动态规划这四个字，我当年绕了两周才敢说自己真正入门。后来给朋友讲题，发现大家卡住的点出奇一致：题解看得懂，代码抄得会，轮到自己写就不知道递推式从哪冒出来的。这事我琢磨了很久，最后总结下来，动态规划其实就三件事——找状态、写转移、定边界。标题里这六道题（找零钱、最大连续子序列和、最长上升子序列、最长公共子序列、最长公共子串、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，末尾元素最小可以是多少。维护一个数组d，d[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 一张表格看懂两者的区别

刷题的时候，如果你确认了是“子串”而不是“子序列”，第一反应就该是不匹配时归零，这能避免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不验证就交。动态规划最容易出现“样例过了、测试挂了”的情况，因为你可能把递推式写错了一个分支。有效方法是自己构造几个小用例，比如n=1、空数组、全部相同元素、容量小于最小物品重量，然后手动跑一遍二维表的前几行，确认每一格都符合你的直觉。

6.3 一个能显著提升DP能力的自查习惯

我强烈建议你在纸上画出DP表的转移过程。别嫌麻烦，找零钱就画一维表，LCS就画两行字符串对应的二维表。画几次之后，你会直观地看到哪些格子是“被等号右边哪一格更新的”，这种视觉记忆比单纯背方程牢固得多。等你能随手画出一张DP表，并且能解释清楚每一格的含义时，你就已经比大多数只会套模板的人强了。

我自己刷动态规划的时候，还有一个小习惯：每个题在AC之后，再写一遍空间优化的版本。因为空间优化版本往往逼着你重新审视“哪些旧状态是真正被需要的”，这个思考过程比多刷五道新题还有用。拿上面的六道题来说，找零钱可以只用一个一维数组，最大连续子序列和可以用滚动变量，LCS虽然常规是二维，但可以用两个一维数组滚动——每优化一次，你对状态的定义和转移依赖就理解得更深一截。

动态规划不是靠看会的，是靠推和踩坑学会的。你有那么一两道题卡住，是好事，多写两遍，就通了。