基础动态规划

动态规划适合具有最优子结构和重叠子问题的问题：先定义状态，再由较小状态推导较大状态。线性 DP 按序列下标、网格坐标等线性阶段转移。

建模步骤

1. 确定阶段，例如处理到第 i 个元素；
2. 定义 dp[i] 的确切含义；
3. 枚举最后一步，写出转移；
4. 给出边界与计算顺序，最后确定答案位置。

经典例：最长递增子序列

令 dp[i] 为以 a[i] 结尾的 LIS 长度。枚举此前位置 j，若 a[j]<a[i]，则 dp[i]=max(dp[i],dp[j]+1)；初值均为 1，答案为所有 dp 的最大值。

int lis(vector<int> a) {
    int n=a.size(), ans=0; vector<int> dp(n,1);
    for(int i=0;i<n;i++) for(int j=0;j<i;j++)
        if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1);
    for(int x:dp) ans=max(ans,x); return ans;
}

时间 O(n²)、空间 O(n)；用维护最小结尾值的贪心加二分可优化为 O(n log n)，但其状态含义不同。

常见线性转移

爬楼梯：dp[i]=dp[i-1]+dp[i-2]；打家劫舍：dp[i]=max(dp[i-1],dp[i-2]+a[i])；网格路径常令 dp[i][j] 表示到格子 (i,j) 的最优值。只依赖上一层时可用滚动数组压缩空间。

整理自 XOJ《基础DP》：状态定义必须包含“范围”和“求什么”，避免把答案、转移和边界混淆。