动态规划

DP 思维框架

动态规划适用条件：① 重叠子问题（同一子问题被多次求解）；② 最优子结构（问题最优解包含子问题最优解）。解题三步：定义状态 → 写出转移方程 → 确定初始值与计算顺序。

解题步骤

1. 状态定义：dp[i] 或 dp[i][j] 代表什么？（通常以「前 i 个…」或「区间 [i,j]…」描述）
2. 转移方程：dp[i] = f(dp[i-1], dp[i-2], ...)，从哪些更小的状态推导而来
3. 初始值：边界情况（dp[0]、dp[1] 等）
4. 计算顺序：保证求 dp[i] 时依赖的 dp[j]（j<i）都已计算
5. 答案位置：dp[n]、dp[n-1] 或 max/min over dp[]

自顶向下 vs 自底向上

常见 DP 类别

• 线性 DP：爬楼梯、打家劫舍、最大子数组
• 背包 DP：0/1 背包、完全背包（硬币找零）
• 网格 DP：唯一路径、最小路径和
• 子序列 DP：LCS、LIS、编辑距离
• 区间 DP：戳气球、矩阵链乘
• 状态机 DP：买卖股票系列
• 树形 DP：打家劫舍 III

线性 DP & 背包

线性 DP 的 dp[i] 只依赖若干前驱状态。背包问题是经典的线性 DP：0/1 背包每件物品只用一次（内层逆序），完全背包每件物品可用无限次（内层正序）。

// LC 53 — Maximum Subarray (Kadane's algorithm)
int maxSubArray(vector<int>& nums) {
    int cur = nums[0], best = nums[0];
    for (int i = 1; i < (int)nums.size(); i++) {
        cur = max(nums[i], cur + nums[i]); // extend or restart
        best = max(best, cur);
    }
    return best;
}

// 0/1 Knapsack — can each item be used at most once?
// weights[i], values[i], capacity W
int knapsack01(vector<int>& w, vector<int>& v, int W) {
    int n = w.size();
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; i++)
        for (int j = W; j >= w[i]; j--) // REVERSE order!
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    return dp[W];
}

// Unbounded Knapsack — item can be used unlimited times
int knapsackUnbounded(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;
    for (int j = 1; j <= amount; j++)
        for (int c : coins)
            if (c <= j && dp[j - c] != INT_MAX)
                dp[j] = min(dp[j], dp[j - c] + 1);
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

典型题目

• 70. 爬楼梯（dp[i] = dp[i-1] + dp[i-2]）
• 198. 打家劫舍（dp[i] = max(dp[i-1], dp[i-2] + nums[i])）
• 53. 最大子数组（Kadane's）
• 416. 分割等和子集（0/1 背包判断可行性）
• 322. 零钱兑换（完全背包求最少硬币数）

空间优化：若 dp[i] 只依赖 dp[i-1]，可用滚动变量将空间从 O(n) 降到 O(1)。背包问题二维 dp 可压缩到一维。

子序列 DP

子序列 DP 通常是二维：dp[i][j] 表示考虑 s1 前 i 个字符与 s2 前 j 个字符时的结果。LCS、编辑距离、最长公共子串都属于此类。

关键公式

• LCS：dp[i][j] = dp[i-1][j-1]+1（若s1[i]==s2[j]），否则 max(dp[i-1][j], dp[i][j-1])
• 编辑距离：dp[i][j] = dp[i-1][j-1]（相等），否则 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
• LIS：O(n²) dp 或 O(n log n) 贪心 + 二分

// Longest Common Subsequence (LCS) — O(mn) time, O(mn) space
int lcs(string& s1, string& s2) {
    int m = s1.size(), n = s2.size();
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    return dp[m][n];
}

// Edit Distance (Levenshtein) — O(mn)
int editDistance(string& w1, string& w2) {
    int m = w1.size(), n = w2.size();
    vector<vector<int>> dp(m+1, vector<int>(n+1));
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            if (w1[i-1] == w2[j-1]) dp[i][j] = dp[i-1][j-1];
            else dp[i][j] = 1 + min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]});
        }
    return dp[m][n];
}

// Longest Increasing Subsequence — O(n log n) greedy + binary search
int lengthOfLIS(vector<int>& nums) {
    vector<int> tails; // tails[i] = smallest tail of IS of length i+1
    for (int x : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x; // replace to maintain smallest tail
    }
    return (int)tails.size();
}

典型题目

• 1143. 最长公共子序列（LCS）
• 72. 编辑距离
• 300. 最长递增子序列（LIS）
• 516. 最长回文子序列

空间优化：二维 dp 若转移只用当前行和上一行，可压缩为一维，注意正/逆序遍历。

区间 & 状态机 DP

区间 DP：dp[i][j] 表示区间 [i,j] 的结果，枚举分割点 k。计算顺序按区间长度从小到大。

// Interval DP template
for (int len = 2; len <= n; len++) {        // enumerate length
    for (int i = 0; i + len - 1 < n; i++) { // enumerate start
        int j = i + len - 1;                 // end
        for (int k = i; k < j; k++) {        // enumerate split point
            dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + cost);
        }
    }
}

状态机 DP：将「持有/不持有股票」等状态显式建模。dp[i][state] 表示第 i 天处于 state 状态时的最优值，在状态间转移。

典型题目

• 312. 戳气球（区间 DP）
• 516. 最长回文子序列（区间 DP）
• 121/122/123/188/309. 买卖股票系列（状态机 DP）
• 337. 打家劫舍 III（树形 DP）

区间枚举顺序：区间 DP 的外层循环枚举区间长度 len（从 2 到 n），内层枚举起点 i，终点 j = i + len - 1。确保计算 dp[i][j] 时所有更短区间已计算完毕。