面试和实际项目里动态规划绝对是被问得最多、也最容易被卡住的算法之一。不管是刷题、校招笔试还是日常写业务代码时需要用到的策略优化你迟早都要跟它正面打交道。C 和动态规划的组合尤其经典C 的数组、vector、STL 在实现状态转移时非常顺手性能也足够强所以很多人刷动态规划的第一语言就选 C。这次我把动态规划的核心思路重新梳理了一遍从最简单的楼梯问题讲起一直聊到 01 背包、最长递增子序列、编辑距离这类高频模型代码全部用 C 给出重点讲清楚“为什么这么设计状态”“为什么循环要这么写”。这篇内容适合有一定 C 基础、但对动态规划还处于“看得懂题解、自己写就卡壳”阶段的朋友也适合想系统回顾一下 DP 框架的开发者。1. 动态规划到底在解决什么问题从数楼梯开始1.1 一个看似简单的递归最经典的入门题就是爬楼梯假设你正在爬 n 层楼梯每次可以跨 1 层或者 2 层问一共有多少种不同的方法爬到楼顶。很多人第一反应是递归因为递推关系非常直观想爬到第 n 层最后一步只有两种可能要么从第 n-1 层跨 1 层要么从第 n-2 层跨 2 层。所以方法总数 f(n) f(n-1) f(n-2)。这个公式结构和斐波那契数列一模一样。用 C 随手写一个递归long long climbStairs(int n) { if (n 2) return n; return climbStairs(n - 1) climbStairs(n - 2); }代码很简单但问题也藏在这里。如果你实际跑一下 n 50这个程序会卡到你怀疑人生。原因在于递归树里大量重复计算f(5) 会去算 f(4) 和 f(3)f(4) 又会去算 f(3) 和 f(2)其中 f(3) 被算了两遍f(2) 被算了更多遍。随着 n 增大重复调用的次数呈指数增长时间复杂度是 O(2^n)这个复杂度在 n 50 时就已经是天文数字。1.2 重复子问题是动态规划的入场券如果你盯着递归树看一会儿会发现一个关键现象每次需要计算 f(k) 时计算过程都是一样的结果也是一样的。既然结果一样我为什么要反复算最直接的优化就是加一个“备忘录”把已经算过的 f(k) 存起来下次直接用。这种写法叫记忆化搜索本质是自顶向下的动态规划思想long long climbStairsMemo(int n, vectorlong long memo) { if (n 2) return n; if (memo[n] ! -1) return memo[n]; memo[n] climbStairsMemo(n - 1, memo) climbStairsMemo(n - 2, memo); return memo[n]; } long long solve(int n) { vectorlong long memo(n 1, -1); return climbStairsMemo(n, memo); }加了这一层缓存之后每个 n 只会被计算一次总计算量从指数级降到了 O(n)。这就是动态规划要解决的核心问题当一个问题存在大量重叠子问题时用记录子问题答案的方式避免重复计算把“递归”变成“递推”。1.3 从递归到递推换一个方向看问题记忆化搜索虽然好理解但实际刷题和面试时大家更习惯直接写自底向上的递推。既然 f(n) 只依赖 f(n-1) 和 f(n-2)那我直接从 f(1)、f(2) 开始一路推到 f(n) 就完了。long long climbStairsDP(int n) { if (n 2) return n; vectorlong long 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 数组是“状态数组”dp[i] 表示爬到第 i 层的方法数dp[1] 1、dp[2] 2 是“边界初始化”dp[i] dp[i-1] dp[i-2] 是“状态转移方程”。后面所有的动态规划问题不管多复杂核心都是围绕这三个东西展开。另外再延伸一句面试常考的点这里其实不需要开整个数组因为当前状态只依赖前两个状态用两个变量滚动更新就能把空间从 O(n) 降到 O(1)。这种空间优化的思路在后面的背包问题里还会再次出现而且是重头戏。2. 拆解动态规划的三板斧状态、转移、初始化2.1 状态定义是决定成败的第一步如果你刷过几道动态规划题会发现最难的不是写代码而是“想不出来状态怎么定义”。我的经验是状态定义直接回答一个问题——“你到底想记录什么”。大部分一维 DP 的状态都长这样dp[i] 表示处理完前 i 个元素或者到第 i 个位置时某个目标值是多少。二维 DP 则通常是 dp[i][j] 表示两个序列/两个维度的某种组合下的结果。比如爬楼梯的 dp[i] 是到达第 i 层的方案数01 背包的 dp[i][j] 是拿了前 i 个物品、背包容量为 j 时能装下的最大价值。有一个实用的技巧先问自己“如果我只知道一部分信息能不能算出答案”。例如爬楼梯问题想知道爬到 n 层的方案数只要知道爬到 n-1 层和 n-2 层的方案数就够了所以一维数组足够。再比如后面讲到的编辑距离想知道两个字符串的最少编辑次数至少得知道两个字符串各自处理到哪个位置所以至少要二维状态。状态定义如果不对后面写得再顺也是错的。遇到不会的题先放下代码多花十分钟琢磨状态想清楚了再动手。这个习惯能帮你少踩很多坑。2.2 转移方程的本质是枚举最后一步很多人觉得转移方程难写其实它的本质是“枚举最后一步的所有可能决策”。以爬楼梯为例到第 n 层最后一步要么跨 1 层要么跨 2 层把这两种情况的子问题答案加起来就得到了总方案数。这其实就是递归关系在递推形式下的表达。再举一个稍微复杂一点的例子LeetCode 上经典的“打家劫舍”问题一排房子每间房里有现金不能偷相邻的两间问最多能偷多少。设 dp[i] 表示偷到前 i 间房子时能获得的最大金额。到第 i 间房子时你只有两个选择不偷这一间那收益就是 dp[i-1]偷这一间那前一间不能偷收益就是 dp[i-2] nums[i]。所以转移方程是dp[i] max(dp[i-1], dp[i-2] nums[i])这个例子里“枚举最后一步的决策”体现得很清楚——关键不是“假设你知道答案”而是“站在最后一个决策点去倒推”。我一直觉得动态规划和贪心算法的核心区别就在这里贪心每一步只做当前看起来最好的选择从来不回头动态规划会把所有可能的选择都算出来然后取最优因为子问题的答案已经算好了不存在“将来的信息缺失”问题。2.3 边界初始化最容易忽视的隐形杀手状态转移方程确定之后剩下的就是边界处理。边界写错了经常出现结果差一两个数、或者数组越界崩溃的情况。爬楼梯的边界是 dp[1] 和 dp[2]打家劫舍的边界是 dp[0]没有房子时收益为 0和 dp[1]只有一间房子时收益就是这间房的价值。边界初始化有这么几条经验可以参考如果 dp[i] 依赖 dp[i-1] 和 dp[i-2]初始化时至少要把前两个位置处理清楚。如果能到达的“起点”不是 0而是数组范围内的某个值多数情况下先给 dp 数组填充一个“无效值”比如 -1、0 或很大的 INT_MAX再单独设置边界。如果状态是从“空”开始的比如 dp[0] 表示什么都没有那么 dp[0] 0 往往是合理起点。另外还有一个细节非常值得注意dp 数组的下标从 0 开始还是从 1 开始会影响很多下标判断。我个人习惯凡是涉及“前 i 个元素”的语义优先让下标从 1 开始这样 dp[0] 天然表示“一个元素都没处理”循环里用 dp[i-1] 去对应实际数组的第 i 个元素逻辑清晰很多。当然这只是一种风格重点是不要一会儿从 0 一会从 1把自己绕晕。2.4 遍历顺序为什么方向这么重要动态规划除了状态和转移还有一个经常被忽略但极其关键的问题遍历顺序。方向写错了得到的结果就是错的而且特别难调试因为编译不会报错、运行也不崩溃只是答案不对。遍历顺序取决于状态依赖的方向。爬楼梯里dp[i] 依赖 dp[i-1] 和 dp[i-2]所以从小到大遍历是对的。01 背包的一维优化里容量必须倒序遍历因为正序遍历会让一个物品被重复选用多次。区间 DP 里则必须按区间长度从小到大遍历因为长区间的答案依赖短区间的答案。判断遍历顺序有一个通用方法画一张二维表表里的每个格子代表一个状态然后看当前格子依赖哪些方向的格子。如果依赖左边和上边就从左上到右下遍历如果依赖下方那遍历顺序就要反过来。这个道理很简单但在实战中稍微复杂一点就容易迷建议遇到二维 DP 时先在草稿纸上画个表格把依赖方向标清楚再写循环。3. C 实战01 背包从二维到一维的完整演进3.1 01 背包问题描述与朴素思路01 背包是动态规划里最经典的模型几乎所有学 DP 的人都会遇到。题目是这样的有 n 个物品每个物品有一个重量 w[i] 和一个价值 v[i]现在有一个容量为 W 的背包问在不超过背包容量的前提下能装入的物品最大总价值是多少。每个物品只能选一次所以叫“01 背包”。很多人第一次看到这个题会想按价值密度排序先装性价比最高的这个思路是贪心但直接反例就是有的物品又轻又值钱、有的又重又不值钱贪心容易漏掉“为了一件大价值物品放弃多件小价值物品”的情况。正确的做法还是动态规划。你需要记录的“状态”是在处理了一部分物品之后、剩余容量不同情况下能达到的最大价值。所以状态设计为dp[i][j] 表示前 i 个物品中选取若干放入容量为 j 的背包时能获得的最大价值。目标答案是 dp[n][W]。3.2 二维 DP 的完整实现考虑第 i 个物品时只有两种情况不选它则 dp[i][j] dp[i-1][j]选它前提是 j w[i]则 dp[i][j] dp[i-1][j-w[i]] v[i]。取两者较大值就行。#include bits/stdc.h using namespace std; int main() { int n 4, W 5; vectorint w {0, 2, 1, 3, 2}; // 下标从 1 开始 vectorint v {0, 3, 2, 4, 2}; vectorvectorint dp(n 1, vectorint(W 1, 0)); for (int i 1; i n; i) { for (int j 0; j W; j) { if (j w[i]) { dp[i][j] dp[i - 1][j]; } else { dp[i][j] max(dp[i - 1][j], dp[i - 1][j - w[i]] v[i]); } } } cout dp[n][W] endl; return 0; }这段代码本身不复杂但有几个地方可以停下来想一想。第一个是容量 j 从 0 遍历到 W为什么不是从 w[i] 开始因为当 j w[i] 时虽然不能选当前物品但仍要延续不选该物品时的价值也就是 dp[i-1][j]所以必须把整个容量区间都覆盖到。第二个是 dp[i][j] 语义是“前 i 个物品”所以 i 这一维是逐一加入物品的过程这个过程保证了每个物品最多只被考虑一次。运行这段代码输入示例的结果是 7选第 1 个、第 2 个和第 4 个物品重量 2125价值 3227。3.3 一维滚动数组为什么要倒序遍历容量二维数组在 n 和 W 都很大时内存消耗很吓人。观察转移方程会发现dp[i][...] 只依赖 dp[i-1][...]也就是只会用到上一层的值那完全可以用一维数组滚动更新。vectorint dp(W 1, 0); for (int i 1; i n; i) { for (int j W; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }这里有一个经典的陷阱内层循环必须从 W 往 w[i] 方向倒序遍历。为什么如果正序遍历比如 j 从小到大那么 dp[j] 可能已经把当前第 i 个物品放进去了然后继续往更大的 j 更新时dp[j-w[i]] 又被更新成了包含第 i 个物品的值这会导致同一个物品被放进背包两次。举个例子w[i]1 时容量从 1 更新到 2dp[2] max(dp[2], dp[1] v[i])而 dp[1] 如果正序遍历已经更新成包含物品 i 的值dp[2] 就等于放了两次物品 i。倒序遍历时dp[j-w[i]] 还没被本轮更新它仍然代表“只考虑前 i-1 个物品”时的状态所以能保证每个物品最多选一次。另外这段代码里没有显式的 if (j w[i]) 分支因为 j 直接从 w[i] 开始倒序j w[i] 的处理就是 dp[j] 保持不变也就是继承上一层 dp[i-1][j]——这在滚动数组里天然成立不用特意写。01 背包最典型的变种有三个完全背包每个物品可无限选择内层正序遍历、多重背包每个物品有数量限制需要二进制拆分或单调队列优化、以及恰好装满背包的情况初始化时把 dp[0] 设为 0其他 dp[j] 设为负无穷。这三个变种面试里出现频率极高建议套着这个基础代码自己推导一遍尤其要搞清楚“为什么完全背包正序遍历就能选无限次”。4. 继续实战最长递增子序列和编辑距离4.1 最长递增子序列LIS最长递增子序列也是动态规划的经典入门题题面很简单给定一个整数数组找出其中最长的严格递增子序列的长度。注意“子序列”不要求连续只要保持相对顺序就行。状态定义dp[i] 表示以第 i 个元素结尾的最长递增子序列长度。为什么是“以 i 结尾”因为只有知道了最后一个元素的位置才能判断下一个候选元素能不能接上去。初始化时每个 dp[i] 至少为 1因为单元素本身就是一个长度为 1 的递增子序列。转移方程对于每个 i遍历 j i如果 nums[j] nums[i]说明第 i 个元素可以接在以第 j 个元素结尾的子序列后面那么 dp[i] max(dp[i], dp[j] 1)。int lengthOfLIS(vectorint nums) { int n nums.size(); vectorint 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; }这段代码的时间复杂度是 O(n^2)空间复杂度 O(n)。面试官大概率会追问一句“能不能优化到 O(n log n)”这里提一下思路维护一个数组 tailstails[k] 表示长度为 k1 的递增子序列中末尾元素的最小值。遍历每个数时用二分查找找到它应该更新的位置从而把查找从 O(n) 降为 O(logn)。这个优化不改变动态规划的本质但属于典型的“状态定义优化后配合数据结构”。LIS 还有一个容易混淆的变种是“最长连续递增子序列”那个用一次遍历就能做不需要动态规划因为它要求子序列在原数组中连续。做题时一定先看清楚“连续”两个字。4.2 编辑距离二维 DP 的典范编辑距离Levenshtein Distance是字符串处理里非常经典的动态规划题。问题描述给你两个单词 word1 和 word2允许执行插入、删除、替换三种操作每次操作的代价都是 1问把 word1 转换成 word2 最少需要多少步操作。为什么这个题天然适合 DP因为两个字符串的比较需要同时关注两个“处理进度”而这个进度天然可以用二维状态表示。设 dp[i][j] 表示 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最小编辑次数。初始化相对好理解dp[i][0] i表示把 word1 的前 i 个字符全部删掉变成空串dp[0][j] j表示从空串逐个插入字符变成 word2 的前 j 个字符。转移分两种情况。如果 word1[i-1] word2[j-1]那么最后一个字符不用操作dp[i][j] dp[i-1][j-1]。如果不相等则有三种处理方式删除 word1 的最后一个字符对应 dp[i-1][j] 1在 word1 末尾插入一个字符对应 dp[i][j-1] 1把 word1 的最后一个字符替换成 word2 的最后一个字符对应 dp[i-1][j-1] 1。取三者最小值。int minDistance(string word1, string word2) { int m word1.size(), n word2.size(); vectorvectorint dp(m 1, vectorint(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 { dp[i][j] min({dp[i - 1][j] 1, dp[i][j - 1] 1, dp[i - 1][j - 1] 1}); } } } return dp[m][n]; }这里有一个很多人会卡住的地方为什么增删改三种操作的转移方向不一样实际上你可以把 dp[i-1][j] 先理解成“word1 的前 i-1 个字符已经是 word2 的前 j 个字符”那多出来的 word1[i-1] 只能删除dp[i][j-1] 理解成“word1 的前 i 个字符已经是 word2 的前 j-1 个字符现在还需要一个字符才能匹配只能插入”dp[i-1][j-1] 则是最后一位直接替换。这样理解之后转移方向记起来就很自然了。编辑距离的变种在真实业务里非常常见比如拼写纠错、DNA 序列对齐、模糊匹配的评分函数都会用到类似思路。如果后面想深入建议研究一下“带权编辑距离”和“最长公共子序列 LCS”之间的关系LCS 可以看作只允许插入和删除的编辑距离问题。4.3 区间 DP 的典型思路合并石子除了序列 DP 和背包 DP区间 DP 是另一个高频模型。经典例子是石子合并有 n 堆石子排成一排每次只能合并相邻的两堆合并的代价是这两堆石子的数量之和问把所有石子合并成一堆的最小总代价。这种题的特点是每次操作的对象是“一段连续的区间”所以状态定义通常为 dp[l][r] 表示把第 l 堆到第 r 堆石子合并成一堆的最小代价。最终答案是 dp[1][n]。转移的时候枚举最后一步是哪两堆合并的。也就是说存在一个分界点 k使得区间 [l, r] 被拆成 [l, k] 和 [k1, r] 两段分别合并后再把这两堆合到一起代价是区间总重量 sum(l, r)。转移方程dp[l][r] min(dp[l][r], dp[l][k] dp[k1][r] sum(l, r))C 实现如下#include bits/stdc.h using namespace std; int main() { int n 4; vectorint w {1, 3, 5, 2}; vectorint prefix(n 1, 0); for (int i 1; i n; i) prefix[i] prefix[i - 1] w[i - 1]; auto sum [](int l, int r) { return prefix[r] - prefix[l - 1]; }; vectorvectorint dp(n 1, vectorint(n 1, INT_MAX)); for (int i 1; i n; i) dp[i][i] 0; for (int len 2; len n; len) { for (int l 1; l len - 1 n; l) { int r l len - 1; for (int k l; k r; k) { dp[l][r] min(dp[l][r], dp[l][k] dp[k 1][r] sum(l, r)); } } } cout dp[1][n] endl; return 0; }注意这里的遍历顺序最外层是区间长度 len从 2 开始然后枚举左端点 l再枚举分界点 k。这跟普通二维 DP 的“从左上到右下”不一样因为长区间的答案依赖短区间的答案只有先算短区间长区间的 dp 子问题才是有效的。如果直接枚举 l 和 r可能会用到尚未计算的长区间值结果必然是错的。区间 DP 初始化也值得记一下l r 时不需要合并代价为 0所以 dp[i][i] 设为 0其余先设为 INT_MAX这样在 min 运算中不会被误选。5. 动态规划调试与常见坑位排查实录5.1 动态规划最容易踩的四个坑写动态规划最容易出错的地方我总结下来主要是下面四个每个我都踩过第一是数组越界。这个最直接尤其是二维 DP 里 i-1、j-w[i] 这种下标稍不注意就越界。解决办法是先把数组长度全部加 1下标从 1 开始同时循环时把所有涉及负下标的分支提前用 if 拦截。第二是初始化错误。常见案例是 dp 数组全 0、或者全 1、或者全 INT_MAX用错了就直接影响最终结果。比如“恰好装满容量 W”的背包问题如果初始化为 0那么装不满的容量也会被当成合法方案参与计算答案就会错误偏大。正确做法是 dp[0] 0其他 dp[j] -INF。第三是转移顺序错误。这个是所有 DP bug 里最难排查的因为结果可能只差一点或者只在某些数据上错。我印象最深的是第一次写完全背包把内层容量循环写成从大到小结果每个物品只能选一次跟 01 背包没有任何区别测试样例还全过了。建议写循环之前先想清楚当前状态依赖的是“上一层”还是“当前层”的数据再决定遍历方向。第四是数据溢出。动态规划结果经常累加或求最大值C 里 int 很容易溢出尤其涉及方案数时。经验是如果题目没有明确说明答案很小优先用 long long拿不准的时候用 long long 不会亏最多多占点内存。5.2 我自己最常用的调试三板斧动态规划的调试有一点特殊因为程序通常不崩溃只是答案不对。如果你也陷在这种困境里我建议按下面三个方法排查先从小数据开始验证。把 n、W、字符串长度这类参数改到 5 以内手动在纸上算一遍再把程序输出打出来对比。这个方法能快速确认思路对不对也能帮你重新梳理状态定义和转移方程。再打印整个 dp 表。在循环结束后把 dp 数组输出到终端观察表里的数值分布是否符合直觉。比如 01 背包里随着容量增大dp[i][j] 不应该出现“更小的容量反而拥有更大价值”这种奇怪现象如果出现了大概率是转移方向或容量边界写错了。打印 dp 表这个动作比盯着代码发呆高效十倍。最后是暴力对拍。写一个最简单的递归枚举版本不要求效率只要求正确然后用随机小数据反复对比动态规划版本和暴力版本的结果。这个方法看起来笨但确实是找边界条件问题的利器。以前我总觉得对拍是竞赛选手才需要做的事后来发现平时改一个状态转移的小细节时对拍能帮我节省大量手工构造样例的时间。5.3 面试里怎么快速判断一道题能不能用动态规划掌握了上面的实战例子之后你可能会想知道拿到一道新题怎么判断它适不适合用动态规划。我的判断标准有两个第一问题是否具有最优子结构。也就是说整体问题的最优解能不能由子问题的最优解组合得到。比如编辑距离里整个字符串的最小编辑次数可以由前面部分字符串的最小编辑次数推出来。如果一个问题的最优解必须依赖“全局信息”而不是“之前几步的信息”那动态规划不一定适用。第二问题是否存在重叠子问题。也就是不同路径的求解过程中会不会反复遇到相同的子问题。如果一道题你用朴素递归写出来发现大量重复计算那它大概率可以用动态规划优化如果递归树根本没有重合那记忆化搜索和动态规划就没什么优势。动态规划不一定要“从上往下想”或者“从下往上想”关键是找到能正确描述状态的维度。状态多了空间复杂度上去了状态少了信息不足转移写不出来。这中间的度只能靠多做题、多复盘来把握。最后再分享一个我自己实际写动态规划时的小习惯每道题写完代码之后我会在注释里写清楚三句话——状态代表什么、初始值是什么、转移方程依赖哪些子状态。这个习惯看着麻烦但真能逼着我把思路理清楚也方便隔几天再回头复习。毕竟动态规划题型的套路性很强把每一道经典题的方法论沉淀下来下次遇到变种脑子里自然就有方向了。