动态规划

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（House Robber III）

每个节点返回两个值：抢该节点的最优解、跳过该节点的最优解，后序遍历自底向上合并。

// LC 337 — House Robber III (Tree DP)
// dfs returns {max_if_rob_root, max_if_skip_root}
pair<int,int> dfs(TreeNode* node) {
    if (!node) return {0, 0};
    auto [rl, sl] = dfs(node->left);
    auto [rr, sr] = dfs(node->right);
    int rob  = node->val + sl + sr;       // rob root → skip both children
    int skip = max(rl, sl) + max(rr, sr); // skip root → take best of each child
    return {rob, skip};
}
int rob(TreeNode* root) {
    auto [r, s] = dfs(root);
    return max(r, s);
}

网格 & 状态机 DP

网格 DP：dp[i][j] 表示到达格子 (i,j) 时的最优值，转移来自上方 dp[i-1][j] 或左方 dp[i][j-1]。按行滚动可将空间从 O(mn) 降到 O(n)。

// LC 62 — Unique Paths: 1D rolling-row (O(n) space)
int uniquePaths(int m, int n) {
    vector<int> dp(n, 1);
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            dp[j] += dp[j-1];
    return dp[n-1];
}

// LC 64 — Minimum Path Sum: rolling row
int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<int> dp(n);
    dp[0] = grid[0][0];
    for (int j = 1; j < n; j++) dp[j] = dp[j-1] + grid[0][j];
    for (int i = 1; i < m; i++) {
        dp[0] += grid[i][0];
        for (int j = 1; j < n; j++)
            dp[j] = min(dp[j], dp[j-1]) + grid[i][j];
    }
    return dp[n-1];
}

状态机 DP

将「持有/刚卖/冷冻」等隐式状态显式建模为 dp 维度。同一天处于不同状态的最优利润相互转移，无需讨论所有情况枚举。

// State Machine DP — Stock with Cooldown (LC 309)
// Three states: hold (holding) / sold (just sold) / rest (idle)
int maxProfitCooldown(vector<int>& prices) {
    int hold = INT_MIN, sold = 0, rest = 0;
    for (int p : prices) {
        int ph = hold, ps = sold, pr = rest;
        hold = max(ph, pr - p);  // buy: must come from rest
        sold = ph + p;           // sell: was holding
        rest = max(pr, ps);      // cooldown ends or stay idle
    }
    return max(sold, rest);
}

// Generic k-transaction framework (LC 188 — at most k txns)
// dp[k][0] = max(dp[k][0], dp[k][1] + price)   // sell
// dp[k][1] = max(dp[k][1], dp[k-1][0] - price) // buy

典型题目

• 62. 不同路径（dp[j] += dp[j-1]，滚动行）
• 64. 最小路径和（min(上, 左) + grid[i][j]）
• 221. 最大正方形（dp[i][j] = min(左, 上, 左上) + 1）
• 309. 含冷冻期买卖股票（3 状态：持有 / 刚卖 / 休息）
• 188. 买卖股票 IV（dp[k][0/1] 通用 k 次框架）

空间优化：网格 DP 按行滚动后空间为 O(n)。状态机 DP 中「状态数 × 天数」通常是常数空间，无需数组。

区间 DP

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

// Interval DP template — enumerate by length
for (int len = 2; len <= n; len++) {         // length from small to large
    for (int i = 0; i + len - 1 < n; i++) { // start index
        int j = i + len - 1;                 // end index
        for (int k = i + 1; k < j; k++) {   // last balloon to burst in (i,j)
            dp[i][j] = max(dp[i][j],
                dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]);
        }
    }
}

典型题目

• 312. 戳气球（dp[i][j] = 最后戳破 k 的最大金币）
• 1312. 最少插入次数使字符串成为回文（dp[i][j]）
• 516. 最长回文子序列（区间 DP）
• 1039. 多边形三角剖分的最低得分（区间 DP）

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