C++ 动态规划入门笔记：状态转移方程与背包问题

动态规划（Dynamic Programming，简称 DP）是算法里最核心的思想之一，竞赛和面试都常考。它专门用来解决“有很多重叠子问题、且问题能拆成最优子结构”的一类题。很多同学一看到 DP 就怕，其实是被“状态”“转移”这些词吓到了——套路固定，练熟了就是送分题。

一、DP 解决什么问题

有些问题如果直接暴力求解会超时，因为重复算了无数次同样的小问题。比如算斐波那契 f(n)=f(n-1)+f(n-2)，暴力递归会把 f(n-2) 算好几遍，时间复杂度指数级爆炸。

DP 的核心就是一句话：把小问题的答案存起来，需要用的时候直接取，不重复算。用空间换时间，把指数级降到多项式级。

和贪心不同：贪心每步取“局部最优”，未必能得到全局最优；DP 是在所有可能的选择里，借助已经算好的子问题答案，找出真正的最优解。和分治也不同：分治（如快排、归并）子问题彼此独立，DP 的子问题是互相重叠、需要复用的。

二、两个关键性质

1. 重叠子问题：大问题拆出的小问题被反复用到。比如爬楼梯，算 f(5) 要 f(4) 和 f(3)，算 f(4) 又要 f(3)——f(3) 被算了两次。
2. 最优子结构：大问题的最优解，可以由小问题的最优解组合得到。

一个问题同时满足这两点，基本就能往 DP 上想。

三、解题四步

做 DP 题有一套固定套路，按这个顺序走不会乱：

1. 定义状态：dp[i] 表示“什么什么到第 i 个为止的最优值”。状态定义对了，题就解了一半。这一步最考验理解，要写清楚 dp[i] 到底代表什么。
2. 写转移方程：dp[i] 怎么由前面的 dp 推出来。这是 DP 的灵魂，想清楚“当前决策有哪些、每种决策对应哪个子问题”。
3. 定初始值：最小的几个 dp 是什么，比如 dp[0]、dp[1]，以及边界情况（比如容量为负、长度为 0）。
4. 定计算顺序：从前往后还是从后往前，保证算 dp[i] 时它依赖的值已经算好。

四、例题 1：爬楼梯

题目：每次可以爬 1 级或 2 级台阶，问爬到第 n 级有几种方法。

思路：dp[i] = 到第 i 级的方法数。最后一步要么从 i-1 跨 1 级，要么从 i-2 跨 2 级，所以 dp[i] = dp[i-1] + dp[i-2]。

int climb(int n) {
    if (n <= 1) return 1;
    int a = 1, b = 1;          // dp[0], dp[1]
    for (int i = 2; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

这里只用两个变量滚动，空间是 O(1)。如果写 dp 数组也能做，但没必要浪费空间。注意这道题其实是斐波那契数列的变种。

五、例题 2：最长上升子序列（LIS）

题目：给一个数组，求最长的严格递增子序列长度（子序列不要求连续）。

状态：dp[i] 表示“以第 i 个数结尾的上升子序列最长是多少”。

转移：看前面所有 j < i 且 a[j] < a[i] 的位置，dp[i] = max(dp[j]) + 1。

int lis(vector<int>& a) {
    int n = a.size();
    vector<int> dp(n, 1);     // 每个数自己至少长度 1
    int ans = 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);
        }
        ans = max(ans, dp[i]);
    }
    return ans;
}

时间复杂度 O(n²)，还有 O(n log n) 的贪心 + 二分写法（维护一个“末尾最小”的辅助数组），进阶时再学。

六、例题 3：0-1 背包

题目：n 件物品，每件有重量 w[i] 和价值 v[i]，背包容量 W，每件最多选一次，求能装下的最大价值。

状态：dp[i][j] 表示“前 i 件物品、容量用了 j 时的最大价值”。

转移：第 i 件选或不选—— dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])（能放得下才选）。

int knapsack(int W, vector<int>& w, vector<int>& v) {
    int n = w.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= W; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= w[i-1])
                dp[i][j] = max(dp[i][j], dp[i-1][j - w[i-1]] + v[i-1]);
        }
    return dp[n][W];
}

空间可优化成一行（滚动数组），从后往前更新 j 即可，避免用到还没更新的旧值。如果改成“每件可以选无限次”，就是完全背包，内层 j 改为从小到大更新。

七、例题 4：数字三角形

题目：从上往下走，每步只能走向下一行相邻的数，求路径数字和最大。

思路：自下而上递推。dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1])。从最后一行开始往上加，最后 dp[0][0] 就是答案。这种“倒着推”常常比正着推更简单，因为它天然满足了计算顺序的要求——底部已经是确定的边界值。

八、例题 5：最长公共子序列（LCS，进阶）

题目：两个字符串，求它们最长的公共子序列长度（不要求连续）。

状态：dp[i][j] 表示“s1 前 i 个字符、s2 前 j 个字符的 LCS 长度”。

转移：若 s1[i-1] == s2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1；否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。这是二维 DP 的经典模板，理解了它，很多“两个序列比较”的题都能套。

九、空间优化：滚动数组

当 dp[i] 只依赖 dp[i-1] 这一层时，可以不存整个二维表，只用一维数组反复覆盖，省内存也常提速。比如背包里用一维数组 f[j] 从大到小更新，本质上就是复用了上一层的状态。注意更新方向：依赖“上一层”就倒序，依赖“本层前面”就正序。

十、DP 与记忆化搜索

DP 的“自底向上”也可以用“自顶向下 + 记忆化”实现：写一个递归函数，把算过的 dp 值存进数组，下次直接返回。两者本质等价，记忆化写起来更像暴力递归、不易错，DP 迭代通常更快、空间更省。新手可以先用记忆化把题做对，再改写成迭代 DP 优化。

十一、调试 DP 的小技巧

• 不确定转移对不对，就把 dp 表打印出来，肉眼看每一行是不是符合预期。
• 用极小的样例（n=3、4）手算一遍答案，再和代码输出对比。
• 注意下标从 0 还是 1 开始，边界（i=0、j=0）有没有处理。

十二、常见 DP 类型速查

• 线性 DP：爬楼梯、LIS、最大子段和。
• 背包 DP：0-1 背包、完全背包（每件无限次）、多重背包。
• 区间 DP：石子合并、括号匹配，常枚举区间长度。
• 树形 DP：在树上做状态转移，先递归处理子树再合并。
• 状态压缩 DP：用二进制位表示状态（进阶）。
• 数位 DP：统计满足某条件的数字个数（进阶）。

十三、易错点

1. 状态定义不清，导致转移写不出。先在纸上把 dp[i] 的含义写明白。
2. 初始值设错，比如该是 0 还是 1，边界没处理好（比如 dp[0] 到底是 0 还是 1）。
3. 计算顺序错，用到的值还没算，结果就是错的。
4. 数组开小了或下标越界，段错误常见来源。
5. 整数溢出：答案可能很大，该用 long long 时用，别偷懒用 int。

十四、练习

1. 斐波那契第 n 项（用 DP 而不是暴力递归）。
2. 最大子段和：连续子数组的最大和（经典线性 DP）。
3. 完全背包：每件物品可以选无限次。
4. 编辑距离（进阶）：两个字符串最少改几次能变一样（增删改三种操作）。
5. 不同路径：机器人从左上到右下，每次只能右或下，问有多少种走法（组合 / DP 均可）。

每道题先按“状态—转移—初始化—顺序”四步列清楚，再写代码，写完用小样例验证。

十六、怎么判断一道题该用 DP

拿到题先问自己两个问题：第一，大问题能不能拆成小问题？第二，这些小问题会不会被反复计算（也就是重叠）？如果两个都是“是”，基本就是 DP 的料。再不行，先试试暴力递归，如果发现同一个参数被算了很多次，就把它记下来——这其实就是 DP 的思想。另一个信号是题目问“最大 / 最小 / 方案数 / 能否”，且选择有先后顺序上的依赖，往往用 DP 而不是贪心。贪心只顾眼前最优，DP 才保证全局最优，这是两者最本质的分界。

十七、背包问题的几个变种

• 0-1 背包：每件最多选一次，一维 dp 从后往前更新，避免本层被重复使用。
• 完全背包：每件可以选无限次，内层 j 从前往后更新。
• 多重背包：每件有数量上限，可拆成多个 0-1 或用二进制优化加速。 记住“能不能重复选”这一个区别，就能决定内层循环的方向，这是背包题最容易写错的地方。刷题时先判断是哪种背包，再套对应写法，几乎不会乱。

十八、状态压缩 DP 简介

当“选了哪些元素”这种状态需要记录，且元素不多（比如不超过 20 个）时，可以用一个整数的二进制位来表示集合：第 i 位是 1 表示选了第 i 个。这样庞大的“选 / 不选”组合就能压缩成一个整数，直接当 dp 数组的下标。听起来很高级，本质还是“用数字编码状态”。初学了解概念即可，遇到旅行商、棋盘覆盖这类题再深入，不要被名词吓住。

十九、完整推导演示：不同路径

题目：m×n 的网格，从左上角走到右下角，每次只能向右或向下，问有多少种走法。状态 dp[i][j] 表示到达第 i 行第 j 列的路径数。转移：只能从左边或上边过来，所以 dp[i][j] = dp[i-1][j] + dp[i][j-1]。初始：第一行和第一列都只有 1 条路（一直向右、或一直向下）。手推算一个小网格，答案恰好是组合数 C(m+n-2, m-1)。把 dp 表打印出来和手算对照，能帮你确认转移方程没写错，这种“小样例手算对比”的习惯非常值钱。

二十、练习拓展

6. 最长公共子序列（LCS）：两个字符串的最长公共子序列长度，用二维 DP，参见上文例题五。
7. 打家劫舍：不能偷相邻的房子，求最大收益，状态是“偷或不偷第 i 家”，经典一维 DP。
8. 买卖股票：给定每天价格，求最大利润，可转化为“找波谷波峰”或 DP 处理。

廿一、给新手的最后提醒与题单

别一上来就背模板。先拿爬楼梯、最大子段和这种简单题，强迫自己严格按四步法写：定义状态、写转移、定初值、定顺序。写不顺就画一张 dp 表，一行一行填，填着填着规律就出来了，转移方程也不再抽象。

下面这张经典题单可以按顺序刷，每道都先在纸上走四步法再写代码：一、斐波那契第 n 项（理解重叠子问题）；二、爬楼梯（最朴素的转移）；三、最大子段和（连续区间 DP）；四、最长上升子序列（二维比较）；五、0-1 背包（二维到一维优化）；六、最长公共子序列（双序列 DP）；七、编辑距离（进阶双序列）。刷题量到了，看到题脑子里会自动冒出“这像是个线性 DP / 背包 DP”，那就是手感来了。动态规划没有天赋能绕过的大量练习，但每做一道，你对“状态”和“转移”的直觉就扎实一分，坚持一个月，曾经头疼的题会变成送分题。

廿二、调试 DP 的额外一招

除了打印 dp 表，还有一个实用的法子：先用记忆化搜索（递归 + 缓存）把题做对，再把它“翻译”成迭代的 DP。两者答案一定相同，你可以拿记忆化版本当对拍工具，验证迭代版本有没有写错。把复杂问题先想成递归，往往比硬凑循环直观得多，尤其在比赛紧张时，这招能救你于水火。很多高手就是靠这招双保险，既快又稳，也更容易在压力下少出错。另外提醒一句：竞赛里 dp 数组如果开在 main 函数内部是占栈空间的，数组太大可能导致栈溢出，必要时开成全局数组或改用 vector，这正是新手常遇到的“本地能过、提交就崩”的隐藏原因之一，值得提前留意。把这两种调试与排错习惯尽早养成，动态规划这条路会走得更顺、也更自信。

小结

学 DP 没有捷径：多做题、多总结“状态怎么定义、转移怎么写”。同一类题做两三道，套路就出来了。记住核心心法——把重复的子问题答案存下来，用空间换时间。遇到题先别急着写代码，在纸上把“状态、转移、初始化、顺序”四步列清楚，往往写着写着就通了。动态规划不是天赋，是练出来的手感。