Interview Prep

动态规划算法题复习笔记

整理 DP 四步法、线性 DP、二维路径 DP、子序列 DP、01 背包与完全背包、字符串 DP、股票 DP，并附一组练习题。

发布于 约 6 分钟算法LeetCode
目录 · 33 节

DP 不像图论只有一个模板，它主要分成几种固定模型：线性、二维路径、子序列、背包、字符串、股票。这篇把这些模型的写法按「dp[i] 是什么 → 初始化 → 转移方程 → 返回」四步法整理在一起，再附上一组练习题。

一、DP 最核心理解

DP 本质就是：

一个大问题，可以拆成很多小问题； 小问题的答案可以被复用。

做 DP 题的固定四步：

1. dp[i] 表示什么
2. 初始状态是什么
3. 状态转移方程是什么
4. 最后返回什么

代码模板：

vector<int> dp(n, 0);

// 初始化
dp[0] = ...;

// 状态转移
for (int i = 1; i < n; i++) {
    dp[i] = ...;
}

// 返回答案
return dp[n - 1];

二、线性 DP 写法

状态只和上一个/上两个状态有关，一维数组就能描述，很多还能用滚动变量把空间压到 O(1)。

1. 爬楼梯模型

典型题：

70 爬楼梯
746 使用最小花费爬楼梯

70. 爬楼梯

每次爬 1 或 2 阶，求爬到第 n 阶的方法数，就是斐波那契。

含义：

dp[i] = 爬到第 i 阶的方法数

转移：

dp[i] = dp[i - 1] + dp[i - 2];

模板：

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }

        vector<int> dp(n + 1, 0);

        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
};

注意 dp 数组要开 n + 1，答案在 dp[n]；n <= 2 直接返回，免得 dp[2] 越界。

746. 使用最小花费爬楼梯

从第 0 阶或第 1 阶出发，爬上去要付所踩台阶的 cost，求跨过楼顶的最小花费。

含义：

dp[i] = 到达第 i 级台阶的最小花费（站在第 i 级上，cost[i] 是迈出这一级才付的，所以 dp[i] 不含 cost[i]）

i 从 0 到 n，n 代表楼顶，所以答案是 dp[n] 不是 dp[n - 1]；起点免费选，dp[0] = dp[1] = 0。

转移：

dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

模板：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();

        vector<int> dp(n + 1, 0);

        dp[0] = 0;
        dp[1] = 0;

        for (int i = 2; i <= n; i++) {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }

        return dp[n];
    }
};

2. 打家劫舍模型

典型题：

198 打家劫舍
213 打家劫舍 II
740 删除并获得点数

198. 打家劫舍

不能偷相邻两间，求最多偷多少。第 i 间两种选择：

不偷 i：dp[i - 1]
偷 i：dp[i - 2] + nums[i]
=> dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

初始化 dp[0] = nums[0]，dp[1] 取前两间的最大值。

模板：

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();

        if (n == 1) {
            return nums[0];
        }

        vector<int> dp(n, 0);

        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);

        for (int i = 2; i < n; i++) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        return dp[n - 1];
    }
};

213. 打家劫舍 II

198 的环形版，第一家和最后一家不能同时偷。拆环成两条直线，各跑一次 198，取较大值：

不偷第一家：robRange(nums, 0, n - 2)
不偷最后一家：robRange(nums, 1, n - 1)
答案取两者较大值

这里顺手用 prev2/prev1 滚动，空间 O(1)：

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();

        if (n == 1) {
            return nums[0];
        }

        return max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
    }

    int robRange(vector<int>& nums, int start, int end) {
        int prev2 = 0;
        int prev1 = 0;

        for (int i = start; i <= end; i++) {
            int cur = max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = cur;
        }

        return prev1;
    }
};

注意 n == 1 要先直接返回，否则两条区间会重复偷同一间。

740. 删除并获得点数

拿走 x 得 x 分，但所有 x - 1 和 x + 1 都不能再拿。先按数值聚合成桶 sum[i]（值为 i 的元素累加），剩下的就是 198：拿了 i 就不能拿 i - 1。

转移：cur = max(prev1, prev2 + sum[i])，同样滚动。

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int maxVal = 0;

        for (int num : nums) {
            maxVal = max(maxVal, num);
        }

        vector<int> sum(maxVal + 1, 0);

        for (int num : nums) {
            sum[num] += num;
        }

        int prev2 = 0;
        int prev1 = 0;

        for (int i = 0; i <= maxVal; i++) {
            int cur = max(prev1, prev2 + sum[i]);
            prev2 = prev1;
            prev1 = cur;
        }

        return prev1;
    }
};

桶数组大小由 nums 最大值决定（上限 10^4，开得起）。

三、二维路径 DP 写法

典型题：

62 不同路径
63 不同路径 II
64 最小路径和
120 三角形最小路径和
931 下降路径最小和

1. 不同路径

62. 不同路径

从左上角走到右下角，只能向右 / 向下，求路径总数。

含义：

dp[i][j] = 走到位置 (i, j) 的路径数量

初始化：dp[i][0] = 1、dp[0][j] = 1，第一行 / 第一列只有一条来路。

转移：

dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

模板：

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 0));

        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }

        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }
};

63. 不同路径 II

在 62 的基础上加障碍物：

障碍格：dp[i][j] = 0（走不到，直接跳过）
非障碍格：照抄 62 的转移

注意第一行 / 第一列初始化要”遇障碍即停”，障碍后面的格走不到，不能跳过障碍继续赋 1。

模板：

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();

        vector<vector<int>> dp(m, vector<int>(n, 0));

        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
            dp[i][0] = 1;
        }

        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
            dp[0][j] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    continue;
                }

                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }
};

2. 最小路径和

64. 最小路径和

从左上角走到右下角，只能向右 / 向下，求路径上数字和的最小值。

含义：

dp[i][j] = 走到 (i, j) 的最小路径和

初始化：dp[0][0] = grid[0][0]，第一行 / 第一列累加前缀和。

转移：

dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];

模板：

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        vector<vector<int>> dp(m, vector<int>(n, 0));

        dp[0][0] = grid[0][0];

        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }

        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }

        return dp[m - 1][n - 1];
    }
};

120. 三角形最小路径和

从上往下走到三角形底层，求最小路径和。技巧：从下往上推，一维数组就够，dp[j] 表示从底层走到当前位置的最小和。

初始化：dp = triangle[n - 1]（最后一行）。

转移（自底向上）：

dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j];

模板：

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();

        vector<int> dp(triangle[n - 1]);

        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j];
            }
        }

        return dp[0];
    }
};

从下往上推不用处理边界，还顺手省掉一维空间；数字可为负也没关系，dp 是用最后一行初始化的，不靠 0 兜底。

931. 下降路径最小和

每一行选一个数，下一行只能走正下方、左下、右下，求贯穿矩阵的最小和。

含义：

dp[i][j] = 落到 (i, j) 的最小路径和

初始化：dp[0][j] = matrix[0][j]。

转移：

dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]) + matrix[i][j];

注意首尾两列要判越界（j > 0 / j + 1 < n）；答案是最后一行的最小值，不是固定角标。

模板：

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();

        vector<vector<int>> dp(n, vector<int>(n, 0));

        for (int j = 0; j < n; j++) {
            dp[0][j] = matrix[0][j];
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int best = dp[i - 1][j];

                if (j > 0) {
                    best = min(best, dp[i - 1][j - 1]);
                }

                if (j + 1 < n) {
                    best = min(best, dp[i - 1][j + 1]);
                }

                dp[i][j] = best + matrix[i][j];
            }
        }

        int ans = dp[n - 1][0];

        for (int j = 1; j < n; j++) {
            ans = min(ans, dp[n - 1][j]);
        }

        return ans;
    }
};

四、子序列 DP 写法

这是面试高频。

典型题：

300 最长递增子序列
1143 最长公共子序列
718 最长重复子数组
1035 不相交的线
53 最大子数组和
674 最长连续递增序列

1. 最长递增子序列 LIS

300. 最长递增子序列

含义：

dp[i] = 以 nums[i] 结尾的最长递增子序列长度

转移：

如果 nums[j] < nums[i]：
dp[i] = max(dp[i], dp[j] + 1)

模板：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();

        vector<int> dp(n, 1);

        int ans = 1;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }

            ans = max(ans, dp[i]);
        }

        return ans;
    }
};

注意：答案不是 dp[n - 1]，最长递增子序列不一定要以最后一个元素结尾，得在过程中取 max。

2. 最长公共子序列 LCS

1143. 最长公共子序列

含义：

dp[i][j] = text1 前 i 个字符 和 text2 前 j 个字符 的最长公共子序列长度

注意这里 dp 开 m + 1 和 n + 1，这样边界好写（空串和任何串的公共子序列都是 0）。

模板：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size();
        int n = text2.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 (text1[i - 1] == text2[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];
    }
};

718. 最长重复子数组

和 LCS 很像，但子数组要求连续，所以含义要钉死在”以谁结尾”上：

dp[i][j] = 以 nums1[i - 1] 和 nums2[j - 1] 结尾的最长公共子数组长度

转移：

如果 nums1[i - 1] == nums2[j - 1]：
    dp[i][j] = dp[i - 1][j - 1] + 1
否则：
    dp[i][j] = 0   // 断了，没法接

模板：

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();

        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        int ans = 0;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    ans = max(ans, dp[i][j]);
                }
            }
        }

        return ans;
    }
};

注意和 LCS 的两个区别：

1. 不相等时置 0，不是取上方 / 左方的最大值
2. 答案在过程中取 max，不是 dp[m][n]

1035. 不相交的线

连线不能相交 ⇔ 连出来的数字对在两个数组里相对顺序一致 ⇔ 就是最长公共子序列。

所以这题是 1143 换皮，代码照抄：

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.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 (nums1[i - 1] == nums2[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];
    }
};

3. 最大子数组和

53. 最大子数组和

含义：

dp[i] = 以 nums[i] 结尾的最大连续子数组和

转移：

dp[i] = max(nums[i], dp[i - 1] + nums[i]);

模板：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();

        vector<int> dp(n, 0);

        dp[0] = nums[0];
        int ans = nums[0];

        for (int i = 1; i < n; i++) {
            dp[i] = max(nums[i], dp[i - 1] + nums[i]);
            ans = max(ans, dp[i]);
        }

        return ans;
    }
};

一句话理解：

前面的和如果是负担，就不要它；如果是收益，就带上它。

注意：dp[0] 和 ans 都得从 nums[0] 起，不能初始化为 0，否则全负数数组会算错。

674. 最长连续递增序列

LIS 的”连续版”，比 LIS 简单得多：断了就重新数。

含义：

dp = 以 nums[i] 结尾的连续递增序列长度

转移：

如果 nums[i] > nums[i - 1]：dp = dp + 1
否则：dp = 1   // 断在这里，从自己重新数

模板：

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int n = nums.size();

        int dp = 1;
        int ans = 1;

        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                dp = dp + 1;
            } else {
                dp = 1;
            }

            ans = max(ans, dp);
        }

        return ans;
    }
};

注意对比：

300 LIS：不要求连续，要回看所有 j < i，O(n^2)
674 连续递增：只看前一个，O(n)

五、背包 DP 写法

背包是 DP 里最模板化的一类。

1. 01 背包

每个物品只能选一次。

典型题：

416 分割等和子集
1049 最后一块石头的重量 II
494 目标和
474 一和零

一维 01 背包模板

vector<int> dp(bagSize + 1, 0);

for (int i = 0; i < items.size(); i++) {
    for (int j = bagSize; j >= weight[i]; j--) {
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

关键点：

01 背包容量 j 必须倒序遍历

因为每个物品只能用一次。

416. 分割等和子集

转化为：

能不能从 nums 里选一些数，使它们的和等于 sum / 2。

也就是 01 背包能不能正好装满容量 target = sum / 2，dp[target] == target 就是能凑出来。

模板：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;

        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }

        if (sum % 2 == 1) {
            return false;
        }

        int target = sum / 2;

        vector<int> dp(target + 1, 0);

        for (int i = 0; i < nums.size(); i++) {
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }

        return dp[target] == target;
    }
};

注意：sum 是奇数直接返回 false，这步不能漏。

1049. 最后一块石头的重量 II

两两石头相撞抵消，问最后最小剩多重。

转化：把石头分成两堆，让两堆重量尽量接近，差就是答案。也就是：

选一些石头，让它们的和尽量接近 sum / 2。01 背包。

模板：

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;

        for (int stone : stones) {
            sum += stone;
        }

        int target = sum / 2;

        vector<int> dp(target + 1, 0);

        for (int i = 0; i < stones.size(); i++) {
            for (int j = target; j >= stones[i]; j--) {
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }

        return sum - 2 * dp[target];
    }
};

494. 目标和

给每个数配 + 或 -，使结果为 target，问有几种配法。

转化：

正号组 P，负号组 N
sum(P) - sum(N) = target
sum(P) + sum(N) = sum
=> sum(P) = (target + sum) / 2

于是变成：选一些数凑出 (target + sum) / 2，问方案数。01 背包，dp[j] 表示凑出 j 的方案数。

模板：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;

        for (int num : nums) {
            sum += num;
        }

        if ((target + sum) % 2 != 0 || target + sum < 0) {
            return 0;
        }

        int bagSize = (target + sum) / 2;

        vector<int> dp(bagSize + 1, 0);

        dp[0] = 1;

        for (int i = 0; i < nums.size(); i++) {
            for (int j = bagSize; j >= nums[i]; j--) {
                dp[j] = dp[j] + dp[j - nums[i]];
            }
        }

        return dp[bagSize];
    }
};

注意：

求方案数：dp[0] = 1，转移用加法
求最大价值：dp[0] = 0，转移用 max

target + sum 为负（即 abs(target) > sum）或为奇数时直接返回 0。

474. 一和零

从字符串数组里选最多个，使选中的串里 0 的总数不超过 m，1 的总数不超过 n。

这是二维费用的 01 背包：容量有两个维度，两层循环都要倒序。

含义：

dp[i][j] = 用 i 个 0、j 个 1 的容量，最多能选几个串

模板：

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        for (const string& s : strs) {
            int zeros = 0;
            int ones = 0;

            for (char c : s) {
                if (c == '0') {
                    zeros++;
                } else {
                    ones++;
                }
            }

            for (int i = m; i >= zeros; i--) {
                for (int j = n; j >= ones; j--) {
                    dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1);
                }
            }
        }

        return dp[m][n];
    }
};

注意：计数的是「串的个数」，不是 0/1 的个数。

2. 完全背包

每个物品可以选无限次。

典型题：

322 零钱兑换
518 零钱兑换 II
279 完全平方数
377 组合总和 IV

完全背包模板

vector<int> dp(bagSize + 1, 0);

for (int i = 0; i < items.size(); i++) {
    for (int j = weight[i]; j <= bagSize; j++) {
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

关键点：

完全背包容量 j 正序遍历

因为一个物品可以反复使用。

322. 零钱兑换

含义：

dp[j] = 凑出金额 j 所需要的最少硬币数量

模板：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);

        dp[0] = 0;

        for (int i = 0; i < coins.size(); i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] = min(dp[j], dp[j - coins[i]] + 1);
            }
        }

        if (dp[amount] == amount + 1) {
            return -1;
        }

        return dp[amount];
    }
};

注意：amount + 1 既当「无穷大」初值又当「凑不出」哨兵，最后判断要和初值对上。

518. 零钱兑换 II

含义：

dp[j] = 凑出金额 j 的组合数

模板：

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);

        dp[0] = 1;

        for (int i = 0; i < coins.size(); i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] = dp[j] + dp[j - coins[i]];
            }
        }

        return dp[amount];
    }
};

注意：

先遍历物品，再遍历容量：组合数
先遍历容量，再遍历物品：排列数

279. 完全平方数

把 n 拆成最少的完全平方数之和。物品就是 1, 4, 9, ...，每个能用无限次——标准完全背包。

含义：

dp[j] = 凑出 j 所需要的最少平方数个数

模板：

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, n + 1);

        dp[0] = 0;

        for (int i = 1; i * i <= n; i++) {
            int square = i * i;

            for (int j = square; j <= n; j++) {
                dp[j] = min(dp[j], dp[j - square] + 1);
            }
        }

        return dp[n];
    }
};

注意：物品循环上界是 i * i <= n，不是 i <= n。

377. 组合总和 IV

从这堆数里凑 target，顺序不同算不同的方案（(1, 2) 和 (2, 1) 算两种）。

顺序敏感就是排列数，循环顺序要反过来：先遍历容量，再遍历物品。

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<unsigned int> dp(target + 1, 0);

        dp[0] = 1;

        for (int j = 1; j <= target; j++) {
            for (int i = 0; i < nums.size(); i++) {
                if (j >= nums[i]) {
                    dp[j] = dp[j] + dp[j - nums[i]];
                }
            }
        }

        return dp[target];
    }
};

注意：

对比 518：518 求组合数，外层是物品；377 求排列数，外层是容量
中间结果可能溢出 int，用 unsigned int 顶住

六、字符串 DP 写法

典型题：

5 最长回文子串
647 回文子串
516 最长回文子序列
72 编辑距离
115 不同的子序列
139 单词拆分

1. 回文子串 DP

647. 回文子串

含义：

dp[i][j] = s[i...j] 是否是回文串（1 是 / 0 否）

转移：

如果 s[i] == s[j]：
    如果 j - i <= 1，直接是回文
    否则看 dp[i + 1][j - 1]

模板：

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();

        vector<vector<int>> dp(n, vector<int>(n, 0));

        int ans = 0;

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s[i] == s[j]) {
                    if (j - i <= 1) {
                        dp[i][j] = 1;
                    } else if (dp[i + 1][j - 1] == 1) {
                        dp[i][j] = 1;
                    }
                }

                if (dp[i][j] == 1) {
                    ans++;
                }
            }
        }

        return ans;
    }
};

注意 i 从后往前，保证 dp[i + 1][j - 1] 先算好；j 从 i 开始。

5. 最长回文子串

和 647 共用同一张 dp[i][j] 表，647 数个数，这题记最长的位置和长度，最后 substr 截出来。

模板：

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();

        vector<vector<int>> dp(n, vector<int>(n, 0));

        int bestStart = 0;
        int bestLen = 1;

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1] == 1)) {
                    dp[i][j] = 1;

                    if (j - i + 1 > bestLen) {
                        bestStart = i;
                        bestLen = j - i + 1;
                    }
                }
            }
        }

        return s.substr(bestStart, bestLen);
    }
};

516. 最长回文子序列

子序列不要求连续，换一张表：

dp[i][j] = s[i ... j] 里最长回文子序列的长度

转移：

如果 s[i] == s[j]：dp[i][j] = dp[i + 1][j - 1] + 2   // 两端一起收进答案
否则：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])     // 丢左端或丢右端

模板：

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();

        vector<vector<int>> dp(n, vector<int>(n, 0));

        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;

            for (int j = i + 1; j < n; j++) {
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[0][n - 1];
    }
};

注意遍历顺序：

i 从后往前，j 从 i + 1 往后
因为 dp[i][j] 依赖下方（dp[i + 1][j]）和左方（dp[i][j - 1]）的格子

2. 编辑距离

72. 编辑距离

含义：

dp[i][j] = word1 前 i 个字符变成 word2 前 j 个字符的最少操作数

初始化：dp[i][0] = i（全删），dp[0][j] = j（全插）。

转移：

如果 word1[i - 1] == word2[j - 1]：dp[i][j] = dp[i - 1][j - 1]   // 末尾相同，不用操作
否则：dp[i][j] = min(插入 dp[i][j - 1], 删除 dp[i - 1][j], 替换 dp[i - 1][j - 1]) + 1

模板：

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();

        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        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 (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    int insertOp = dp[i][j - 1] + 1;
                    int deleteOp = dp[i - 1][j] + 1;
                    int replaceOp = dp[i - 1][j - 1] + 1;

                    dp[i][j] = min(insertOp, min(deleteOp, replaceOp));
                }
            }
        }

        return dp[m][n];
    }
};

115. 不同的子序列

问 s 的子序列里有多少个恰好等于 t。

含义：

dp[i][j] = s 前 i 个字符里，能凑出 t 前 j 个字符的方案数

转移：

如果 s[i - 1] == t[j - 1]：
    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
    // 用这个字符 + 不用这个字符
否则：
    dp[i][j] = dp[i - 1][j]
    // 只能不用

模板：

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size();
        int n = t.size();

        vector<vector<unsigned long long>> dp(m + 1, vector<unsigned long long>(n + 1, 0));

        for (int i = 0; i <= m; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s[i - 1] == t[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[m][n];
    }
};

注意：

dp[i][0] = 1 整列都要初始化：空串 t 永远是 s 的子序列，只有一种取法
中间结果可能溢出，用 unsigned long long 顶住（题目保证答案在 int 内）

139. 单词拆分

问 s 能不能被拆成字典里的单词。单词可以反复用——完全背包；而且要按顺序拼——先遍历容量。

含义：

dp[j] = s 前 j 个字符能不能被拆分（1 能 / 0 不能）

转移：

如果存在单词 word：
    j >= len(word) 且 dp[j - len(word)] 可行 且 s[j - len ... j - 1] == word
    则 dp[j] = 1

模板：

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();

        vector<int> dp(n + 1, 0);

        dp[0] = 1;

        for (int j = 1; j <= n; j++) {
            for (const string& word : wordDict) {
                int len = word.size();

                if (j >= len && dp[j - len] == 1 && s.substr(j - len, len) == word) {
                    dp[j] = 1;
                }
            }
        }

        return dp[n];
    }
};

七、股票 DP 写法

典型题：

121 买卖股票的最佳时机
122 买卖股票的最佳时机 II
123 买卖股票的最佳时机 III
188 买卖股票的最佳时机 IV
309 最佳买卖股票时机含冷冻期
714 买卖股票的最佳时机含手续费

最基础的是状态机 DP。

121. 只能买卖一次

扫一遍维护历史最低价，每天尝试「今天卖、历史最低价买」，取最大。贪心即可，不用 dp。

模板：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice = prices[0];
        int ans = 0;

        for (int i = 1; i < prices.size(); i++) {
            ans = max(ans, prices[i] - minPrice);
            minPrice = min(minPrice, prices[i]);
        }

        return ans;
    }
};

注意不交易收益为 0，ans 从 0 起，全跌时返回 0。

122. 可以买卖多次

无限次交易，只要今天比昨天贵就「昨天买、今天卖」，正差价全加起来。

模板：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;

        for (int i = 1; i < prices.size(); i++) {
            if (prices[i] > prices[i - 1]) {
                ans += prices[i] - prices[i - 1];
            }
        }

        return ans;
    }
};

股票题先记这两个贪心就够了。下面是通用的状态机 DP，123 / 188 / 309 / 714 都是它的变形。

1. 状态机模板

每天都只有两个状态：

dp[i][0] = 第 i 天结束后，手里持有股票的最大收益
dp[i][1] = 第 i 天结束后，手里不持有股票的最大收益

转移：

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);   // 昨天就拿着，或今天买
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);   // 昨天就没有，或今天卖

初始化：dp[0][0] = -prices[0]（第一天买入），dp[0][1] = 0。

只依赖前一天，实际写的时候用两个变量滚动。后面的题全是这套骨架上加规则。

122. 可以买卖多次（状态机版）

无限次交易的模板落地，hold / cash 两个变量滚动。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int hold = -prices[0];
        int cash = 0;

        for (int i = 1; i < prices.size(); i++) {
            hold = max(hold, cash - prices[i]);
            cash = max(cash, hold + prices[i]);
        }

        return cash;
    }
};

123. 最多买卖两次

最多两笔交易，把「第几次交易」也编进状态，四个状态滚动：

buy1  = 第一次持有
sell1 = 第一次卖出后
buy2  = 第二次持有
sell2 = 第二次卖出后

初始化：buy1 = buy2 = -prices[0]，sell1 = sell2 = 0。

模板：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy1 = -prices[0];
        int sell1 = 0;
        int buy2 = -prices[0];
        int sell2 = 0;

        for (int i = 1; i < prices.size(); i++) {
            buy1 = max(buy1, -prices[i]);
            sell1 = max(sell1, buy1 + prices[i]);
            buy2 = max(buy2, sell1 - prices[i]);
            sell2 = max(sell2, buy2 + prices[i]);
        }

        return sell2;
    }
};

注意更新顺序不能乱：buy1 → sell1 → buy2 → sell2，后面的状态用上当天前面的更新（允许同一天先卖后买）。

188. 最多买卖 k 次

把 123 的四个状态推广成两个长度为 k + 1 的数组，123 就是 k = 2 的特例。

模板：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();

        if (n == 0 || k == 0) {
            return 0;
        }

        k = min(k, n / 2);   // 最多 n/2 次完整交易，k 再大也没用，先剪枝防 MLE

        vector<int> buy(k + 1, -prices[0]);
        vector<int> sell(k + 1, 0);

        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                buy[j] = max(buy[j], sell[j - 1] - prices[i]);
                sell[j] = max(sell[j], buy[j] + prices[i]);
            }
        }

        return sell[k];
    }
};

注意 k 上限是 10^9，不先 k = min(k, n / 2) 剪枝会开出超大数组，直接 MLE。

309. 含冷冻期

卖出后第二天才能再买，把「不持有」拆成两个状态：

hold   = 持有
cash   = 不持有，且明天不在冷冻期（可以买）
frozen = 不持有，且明天处于冷冻期（刚卖的第二天）

模板：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int hold = -prices[0];
        int cash = 0;
        int frozen = 0;

        for (int i = 1; i < prices.size(); i++) {
            int prevCash = cash;

            cash = max(cash, frozen);
            frozen = hold + prices[i];
            hold = max(hold, prevCash - prices[i]);
        }

        return max(cash, frozen);
    }
};

注意买入只能从不冷冻的 cash 来，所以更新 cash 前先把旧值存进 prevCash。

714. 含手续费

每笔卖出扣一次手续费，在 cash 的转移里减掉就行。

模板：

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int hold = -prices[0];
        int cash = 0;

        for (int i = 1; i < prices.size(); i++) {
            hold = max(hold, cash - prices[i]);
            cash = max(cash, hold + prices[i] - fee);
        }

        return cash;
    }
};

注意手续费只扣一次，放在卖出（cash）这一侧，买入侧不用动。

八、DP 题单加入总题单

1. DP 最小必刷 20 题

70 爬楼梯
746 使用最小花费爬楼梯
198 打家劫舍
213 打家劫舍 II
62 不同路径
63 不同路径 II
64 最小路径和
53 最大子数组和
300 最长递增子序列
1143 最长公共子序列
718 最长重复子数组
416 分割等和子集
494 目标和
322 零钱兑换
518 零钱兑换 II
279 完全平方数
139 单词拆分
647 回文子串
516 最长回文子序列
72 编辑距离

九、完整练习题单

你要”齐全”的话，按这个刷。

1. 第一组：数组 / 双指针 / 滑窗

1 两数之和
26 删除有序数组中的重复项
27 移除元素
283 移动零
11 盛最多水的容器
42 接雨水
3 无重复字符的最长子串
209 长度最小的子数组
438 找到字符串中所有字母异位词

2. 第二组：栈 / 单调栈

20 有效的括号
155 最小栈
232 用栈实现队列
739 每日温度
496 下一个更大元素 I
503 下一个更大元素 II
84 柱状图中最大的矩形

3. 第三组：链表

206 反转链表
92 反转链表 II
21 合并两个有序链表
141 环形链表
142 环形链表 II
160 相交链表
19 删除链表的倒数第 N 个结点
234 回文链表

4. 第四组：二叉树

144 二叉树的前序遍历
94 二叉树的中序遍历
145 二叉树的后序遍历
102 二叉树的层序遍历
104 二叉树的最大深度
111 二叉树的最小深度
226 翻转二叉树
101 对称二叉树
543 二叉树的直径
236 二叉树的最近公共祖先

5. 第五组：堆 / 优先队列

215 数组中的第 K 个最大元素
347 前 K 个高频元素
295 数据流的中位数
23 合并 K 个升序链表
973 最接近原点的 K 个点

6. 第六组：图论

841 钥匙和房间
1971 寻找图中是否存在路径
547 省份数量
200 岛屿数量
695 岛屿的最大面积
994 腐烂的橘子
542 01 矩阵
417 太平洋大西洋水流问题
207 课程表
210 课程表 II
802 找到最终的安全状态
310 最小高度树

7. 第七组：并查集

547 省份数量
1971 寻找图中是否存在路径
684 冗余连接
1319 连通网络的操作次数
990 等式方程的可满足性
721 账户合并

8. 第八组：回溯

46 全排列
47 全排列 II
77 组合
78 子集
90 子集 II
39 组合总和
40 组合总和 II
131 分割回文串
93 复原 IP 地址
51 N 皇后

9. 第九组：DP

70 爬楼梯
746 使用最小花费爬楼梯
198 打家劫舍
213 打家劫舍 II
62 不同路径
63 不同路径 II
64 最小路径和
53 最大子数组和
300 最长递增子序列
1143 最长公共子序列
718 最长重复子数组
416 分割等和子集
494 目标和
322 零钱兑换
518 零钱兑换 II
279 完全平方数
139 单词拆分
647 回文子串
516 最长回文子序列
72 编辑距离

十、推荐刷题顺序

别按 Hot100 顺序乱刷。你现在应该这样来：

1. BFS / DFS / 图论
200 -> 695 -> 994 -> 542 -> 207 -> 210

2. 二叉树
102 -> 104 -> 226 -> 101 -> 543 -> 236

3. 栈 / 单调栈
20 -> 739 -> 496 -> 503 -> 84

4. 链表
206 -> 21 -> 141 -> 142 -> 19 -> 92

5. DP 入门
70 -> 746 -> 198 -> 62 -> 64 -> 53

6. DP 进阶
300 -> 1143 -> 416 -> 322 -> 518 -> 647 -> 72

7. 回溯
46 -> 78 -> 77 -> 39 -> 131 -> 51

8. 堆
215 -> 347 -> 295 -> 23

十一、DP 总结

dp[i] 是什么？
初始化谁？
从哪里转移过来？
循环顺序怎么写？
答案在哪里？

再具体一点：

线性 DP：通常从前往后
二维路径 DP：通常从左上到右下
子序列 DP：通常 i、j 双循环
01 背包：容量倒序
完全背包：容量正序
回文 DP：i 从后往前，j 从 i 往后

最重要的是这两个：

01 背包：for j = target; j >= nums[i]; j--
完全背包：for j = coins[i]; j <= amount; j++

这个背下来，DP 至少不会完全懵。