动态规划这四个字我当年绕了两周才敢说自己真正入门。后来给朋友讲题发现大家卡住的点出奇一致题解看得懂代码抄得会轮到自己写就不知道递推式从哪冒出来的。这事我琢磨了很久最后总结下来动态规划其实就三件事——找状态、写转移、定边界。标题里这六道题找零钱、最大连续子序列和、最长上升子序列、最长公共子序列、最长公共子串、0-1背包我把它们放在一起对比着讲你会看到它们背后的套路惊人地一致。这篇文章适合刚学完递归、想系统入门动态规划的读者也适合刷题刷到一半、总觉得“背了模板也不会用”的朋友。1. 先别急着背模板动态规划的三连问是什么很多人学动态规划上来就找“状态转移方程怎么写”这是本末倒置。我习惯先把一个问题拆成三个问题当前这一步的状态怎么表示它能从哪些更小的状态推过来最小的那个状态是多少这三个问题对应着状态定义、转移方程、初始条件和边界处理三件事搞清楚代码只是最后一哆嗦。1.1 为什么动态规划总让人感觉“玄”因为大多数教程都是直接甩出一个二维数组告诉你dp[i][j]表示什么然后递推公式一拍仿佛这个数组天生就该长这样。但实际上动态规划的本质是把一个大问题拆成相互重叠的子问题并且记住子问题的答案。它和递归最大的区别在于递归是“算完了再回溯”动态规划是“从小往大垒每一步都站在之前的结果上”。拿爬楼梯举例一次可以上1级或2级问爬到第n级有几种走法。你在第n级要么从n-1级迈一步上来要么从n-2级迈两步上来所以f(n) f(n-1) f(n-2)。这里的状态就是“爬到第k级的走法数”转移就是那一步的两种可能边界就是f(1)1、f(2)2。这个例子太过经典反而容易被忽略其实后面六个问题全是这个套路。1.2 状态定义才是真正的分水岭状态定义决定了你后面能不能写出递推式。很多题难不是难在递推而是难在你没想到用那个维度去描述问题。比如最长公共子序列你要用“两个字符串各自的前缀”来描述状态这一下子就变成二维问题了0-1背包你要用“前i件物品、容量为j”来描述状态这又是一个二维问题。这里分享一个我常用的方法拿到题目后先问自己最终答案是什么它跟哪几个变量有关找零钱问题的答案是“凑出amount元所需的最少硬币数”它只跟amount这个变量有关所以是一维DP最长公共子序列的答案是“两个字符串的最长公共子序列长度”它跟两个字符串的已处理长度有关所以至少是二维DP。这个思路不能保证一定对但至少能把绝大多数题的维度定下来。2. 找零钱和最大连续子序列和一个硬币一个数组同一个套路这两个题看起来八竿子打不着一个是硬币组合一个是数组求和但它们的递推思想高度相似都是以“以某个位置/某个量结尾”来定义子问题然后用“最后一个动作”来写转移。2.1 找零钱从目标金额倒着想题目是这样的给定一组硬币面额coins和一个总金额amount求凑出该金额所需的最少硬币数量如果凑不出来返回 -1。假设硬币数量无限。状态定义就是dp[i]表示“凑出 i 元所需的最少硬币数”。那凑出 i 元最后一枚硬币可能是面额为coin的任意一枚所以只要i coin就有一种可能是“凑出i - coin元再加上这枚硬币”。于是转移方程dp[i] min(dp[i - coin] 1) 对所有 coin i初始条件是dp[0] 0因为凑0元不需要任何硬币。其他位置我没法预先知道能不能凑出来就设成一个很大的数比如float(inf)表示“当前还没找到可行方案”。def coinChange(coins, amount): dp [float(inf)] * (amount 1) dp[0] 0 for i in range(1, amount 1): for coin in coins: if i coin: dp[i] min(dp[i], dp[i - coin] 1) return dp[amount] if dp[amount] ! float(inf) else -1这里有个细节值得多说一句为什么从小到大遍历i因为dp[i]只依赖更小的dp[i - coin]只要保证更小的金额先算出来当前金额就能直接查表。这也是动态规划里最常见的遍历原则——先算被依赖的再算依赖别人的。2.2 最大连续子序列和Kadane算法的核心直觉题目给一个整数数组比如[-2, 1, -3, 4, -1, 2, 1, -5, 4]求具有最大和的连续子数组返回其最大和。这个题如果不用DP最暴力的做法是枚举起点和终点O(n²)复杂度。但稍微一想任意一个连续子数组必然以一个元素结尾。那我就定义dp[i]为“以第 i 个元素结尾的最大连续子数组和”。关键的问题是以nums[i]结尾要么它自己单独成一个子数组要么它接在dp[i-1]对应的那个子数组后面。两者取大的那个dp[i] max(nums[i], dp[i-1] nums[i])为什么不是dp[i-1]本身因为子数组必须连续dp[i-1]对应的子数组如果和是负数硬接上nums[i]反而拖累结果所以宁可只选nums[i]自己。初始条件dp[0] nums[0]答案是所有dp[i]里的最大值。def maxSubArray(nums): dp [0] * len(nums) dp[0] nums[0] for i in range(1, len(nums)): dp[i] max(nums[i], dp[i - 1] nums[i]) return max(dp)理论上空间复杂度可以进一步压到 O(1)因为dp[i]只依赖dp[i-1]。这就是滚动变量的思路用一个prev记录上一个结果一个res记录全局最大。空间优化是后面背包问题的预演先在这里埋个伏笔。2.3 这两个题放在一起看套路是什么一个是“凑出金额 i”一个是“以元素 i 结尾”本质上都是用一维数组解决问题并且转移只依赖前一个或前几个状态。找零钱依赖dp[i-coin]相当于跳着依赖最大连续子序列和依赖dp[i-1]是紧挨着的依赖。它们都遵循同一个心法把大问题拆成“最后一步 前面的子问题”并且子问题之间是重叠的所以可以用数组记录。3. 最长上升子序列从暴力到贪心二分查找到底发生了什么最长上升子序列LIS是一个被讲烂了但每次考试都换着花样考的题。它有两种经典解法O(n²)的DP和O(nlogn)的贪心二分。我建议先把第一种写熟再去理解第二种因为第二种的“正确性”不是那么直观。3.1 第一种方案O(n²)的动态规划思路最接近直觉定义dp[i]为“以nums[i]结尾的最长上升子序列长度”。那么只要前面存在一个nums[j] nums[i]并且j i就可以把nums[i]接到以nums[j]结尾的上升子序列后面长度变成dp[j] 1。对所有满足条件的j取最大值实在没有就以自己为开头长度为1。dp[i] max(1, 1 max(dp[j])) 对所有 j i 且 nums[j] nums[i]def lengthOfLIS(nums): n len(nums) dp [1] * n for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp) if n else 0这个写法的好处是状态定义直白几乎不需要解释。坏处也很明显两层循环O(n²)复杂度当 n 到几万时就跑不动了。所以面试里如果只要求写DP这个版本够了但如果数据规模大得拿出第二种方案。3.2 第二种方案贪心 二分查找为什么它能保证正确第二种方案的思路完全换了角度我不关心具体的子序列长什么样我只关心对于每个长度 k末尾元素最小可以是多少。维护一个数组dd[k]表示长度为 k 的最长上升子序列的最小末尾元素。d天然是单调递增的因为长度越大末尾至少不会更小。遍历每个元素x在d里找到第一个大于等于x的位置pos。如果pos存在就把那个位置的数替换成x因为同样长度用更小的末尾元素更优如果x比d里所有元素都大就把它追加到末尾说明最长长度增加1。最终d的长度就是LIS长度。import bisect def lengthOfLIS(nums): d [] for x in nums: pos bisect.bisect_left(d, x) if pos len(d): d.append(x) else: d[pos] x return len(d)我一开始怎么也想不通这个数组并不是真实的子序列为什么最终长度是对的后来想明白了关键在于替换操作是对“上升”性质的加强而不是破坏。每次替换只让末尾元素变小或不变不会让单调性失效长度也只在追加时增加。而追加的前提是x比已知所有最小末尾都大这确实说明存在一条长度为len(d)1的上升子序列。所以长度就是正确答案。3.3 面试/刷题时应该怎么取舍我个人建议先写O(n²)版本保底如果面试官要求优化再上二分版本。因为O(n²)版本逻辑简单不容易在紧张时写错而二分版本虽然快但bisect_left和bisect_right选错会直接导致答案错误。日常刷题数据范围在几千以内O(n²)完全够用数据范围到十万级别就必须用第二种了。这里还要提醒一句LIS的二分版本求的是“严格上升”如果是“非递减”要把bisect_left换成bisect_right细节差一个字母结果天壤之别。4. 最长公共子序列和最长公共子串一个字符之差引发的递推分歧这两个题长得几乎一样但解法在关键位置出现了分叉。很多人把两者搞混面试时被追问一句“子串和子序列的区别”就露馅了。子序列不要求连续子串必须连续。这个区别直接决定了转移方程里那一个字符的处理方式。4.1 最长公共子序列LCS允许跳着匹配问题描述给定两个字符串text1和text2返回它们的最长公共子序列长度。比如abcde和ace公共子序列是ace长度3。状态定义是二维的dp[i][j]表示text1的前 i 个字符和text2的前 j 个字符的最长公共子序列长度。这里前 i 个字符通常用下标范围[0, i-1]来表示可以方便地处理空字符串的情况。转移分两种情况如果text1[i-1] text2[j-1]说明最后一个字符可以匹配上那就在dp[i-1][j-1]的基础上加1。如果不相等匹配不上那答案要么来自text1少看一个字符要么来自text2少看一个字符取较大者。dp[i][j] dp[i-1][j-1] 1 if text1[i-1] text2[j-1] dp[i][j] max(dp[i-1][j], dp[i][j-1]) otherwise初始条件dp[0][j] 0、dp[i][0] 0表示任意一个字符串为空时公共子序列长度为0。def longestCommonSubsequence(text1, text2): m, n len(text1), len(text2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): 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]这里我最想强调的是不相等时为什么取max(dp[i-1][j], dp[i][j-1])因为公共子序列不要求连续即使当前两个字符不同也可能在text1的前i-1个字符和text2的前j个字符里或者text1的前i个字符和text2的前j-1个字符里取最大值才不会漏掉最优解。4.2 最长公共子串必须连续不匹配就得归零如果题目改成“最长公共子串”转移就变成了另一副面孔dp[i][j]表示以text1[i-1]和text2[j-1]作为结尾的公共子串长度。两个字符相等长度在dp[i-1][j-1]基础上加1一旦不相等这段连续关系被打破值直接归0因为以这两个字符结尾的公共子串根本不存在。def longestCommonSubstring(a, b): m, n len(a), len(b) dp [[0] * (n 1) for _ in range(m 1)] res 0 for i in range(1, m 1): for j in range(1, n 1): if a[i - 1] b[j - 1]: dp[i][j] dp[i - 1][j - 1] 1 res max(res, dp[i][j]) else: dp[i][j] 0 return res注意答案不再是dp[m][n]而是整个二维数组里的最大值。为什么呢因为最长公共子串不一定以两个字符串的末尾结尾它可能出现在中间的某个位置。我以前有个同学在这里犯过错直接return dp[m][n]结果拿abcdef和zabcde一测就出问题。4.3 一张表格看懂两者的区别对比项最长公共子序列LCS最长公共子串连续性不要求连续要求连续不匹配时的处理取左边和上边的最大值归零最终答案dp[m][n]max(dp[i][j])能否通过回溯还原子序列/子串可以但较复杂可以记录最大位置即可刷题的时候如果你确认了是“子串”而不是“子序列”第一反应就该是不匹配时归零这能避免80%的错误。5. 0-1背包从二维DP到一维滚动数组变化的核心在遍历顺序0-1背包是动态规划里最经典、最常考的一类。它是理解“背包问题”整个家族的基石后面的完全背包、多重背包、分组背包全都是在0-1背包的基础上改条件。题目描述是有 n 件物品每件物品有重量w[i]和价值v[i]背包容量为C每件物品最多取一次问能装下的最大总价值。5.1 二维DP把“前i件物品”和“容量j”同时放进状态定义dp[i][j]为“考虑前 i 件物品背包容量为 j 时能获得的最大价值”。对第 i 件物品只有两种选择不拿那就是dp[i-1][j]拿那需要腾出w[i]的空间价值变成dp[i-1][j-w[i]] v[i]。两者取最大值dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])def knapsack01(weights, values, capacity): n len(weights) dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): w, v weights[i - 1], values[i - 1] for j in range(capacity 1): dp[i][j] dp[i - 1][j] if j w: dp[i][j] max(dp[i][j], dp[i - 1][j - w] v) return dp[n][capacity]二维写法的好处是逻辑清楚不容易出错特别适合考试或者压力面试时先用它稳住局面。坏处是空间复杂度 O(n*C)当 n 是几千、C 是几万时内存会爆掉。这时候就要上一维滚动数组。5.2 一维优化之后为什么必须倒序遍历写成一维dp[j]表示容量为 j 时的最大价值。每一轮遍历物品 i更新dp[j]。关键来了遍历容量 j 时必须从大到小也就是倒序遍历。为什么因为dp[j]要用到dp[j-w[i]]这个值必须是“还没把当前物品算进去”的旧值。如果正序遍历dp[j-w[i]]可能已经在同一轮里被更新过等于这个物品被用了不止一次那就变成完全背包了。倒序遍历时j-w[i]小于j而在倒序中它还没被本轮更新所以读到的仍然是上一轮的值。def knapsack01_optimized(weights, values, capacity): dp [0] * (capacity 1) for i in range(len(weights)): w, v weights[i], values[i] for j in range(capacity, w - 1, -1): dp[j] max(dp[j], dp[j - w] v) return dp[capacity]这里顺便把完全背包的坑也填了如果物品可以取无限次遍历容量时就该正序因为它刻意允许dp[j-w[i]]是同一轮更新过的值这样就能反复使用同一物品。一道题里正序还是倒序直接决定它是0-1背包还是完全背包这是面试官最爱追问的点。5.3 初始化条件背后的语义陷阱二维和一维版本里dp[0]0表示背包不装任何东西时价值为0天经地义。但有些变形题要求“背包必须恰好装满”这时候不能把所有位置都初始化为0而要dp[0]0其他位置设为-inf或一个足够小的负数。为什么因为-inf表示“用前 i 件物品恰好凑出这个容量是不可能的”。如果全初始化为0那些“没装满”的状态也会被当成合法状态参与转移最终结果看起来是最大值实际上可能是背包没装满的状态。这个细节我在实际比赛里吃过亏一道包装成“求恰好装满容量的最大价值”的题我因为初始化偷懒答案整整偏大了一截。后来每次写背包题我都要先确认题目说的是“容量不超过C”还是“容量恰好为C”。6. 怎么把这一整套动态规划真的吃进去刷题顺序与自我验证方法讲完六个经典题如果你只是收藏了这篇文章那等于没看。动态规划必须在纸上推一遍、在代码里跑一遍才能真正变成自己的东西。最后这部分我分享一下自己带新人时常用的学习路线和踩坑总结。6.1 推荐的练习顺序从同构题开始再逐步加难度我建议的顺序是爬楼梯 → 最大连续子序列和 → 找零钱 → 0-1背包 → LIS → LCS → 最长公共子串。前两个是“一维递推”的入门动作最小找零钱开始出现“从多个子问题里选最优”的思路0-1背包把维度拉到二维并引入“选还是不选”的决策LIS和LCS则进一步训练你对“状态定义”的把握尤其是LCS它几乎是所有字符串DP问题的基石。最长公共子串放在最后是因为它和LCS长得像但细节不同能检验你是真懂了两者的区别还是只是记住了代码。6.2 我见过的五类最常见错误第一类状态定义含糊。比如把LIS的dp[i]写成“前 i 个元素的最长上升子序列长度”而不是“以第 i 个元素结尾的最长上升子序列长度”前者递推起来会非常别扭因为你不知道当前元素到底要不要接上去。第二类初始化和边界漏写。二维DP最容易漏掉dp[0][j]和dp[i][0]这两行虽然Python里用列表推导初始化为0通常能蒙混过关但一旦答案是负值时漏边界就会算错。第三类滚动数组优化时遍历顺序搞反。0-1背包倒序、完全背包正序这个口诀背下来只是第一步关键是要理解倒序是为了不重复使用同一件物品。第四类数组越界和下标偏移没处理妥当。LCS和背包里由于用i-1表示第 i 个字符或物品代码里到处都是i-1和j-1稍不留神就越界。我写这类题的习惯是先把维度都加1所有循环从1开始把i-1统一对应到真实的第 i 个元素。第五类写完DP不验证就交。动态规划最容易出现“样例过了、测试挂了”的情况因为你可能把递推式写错了一个分支。有效方法是自己构造几个小用例比如n1、空数组、全部相同元素、容量小于最小物品重量然后手动跑一遍二维表的前几行确认每一格都符合你的直觉。6.3 一个能显著提升DP能力的自查习惯我强烈建议你在纸上画出DP表的转移过程。别嫌麻烦找零钱就画一维表LCS就画两行字符串对应的二维表。画几次之后你会直观地看到哪些格子是“被等号右边哪一格更新的”这种视觉记忆比单纯背方程牢固得多。等你能随手画出一张DP表并且能解释清楚每一格的含义时你就已经比大多数只会套模板的人强了。我自己刷动态规划的时候还有一个小习惯每个题在AC之后再写一遍空间优化的版本。因为空间优化版本往往逼着你重新审视“哪些旧状态是真正被需要的”这个思考过程比多刷五道新题还有用。拿上面的六道题来说找零钱可以只用一个一维数组最大连续子序列和可以用滚动变量LCS虽然常规是二维但可以用两个一维数组滚动——每优化一次你对状态的定义和转移依赖就理解得更深一截。动态规划不是靠看会的是靠推和踩坑学会的。你有那么一两道题卡住是好事多写两遍就通了。