动态规划绝对是数据结构与算法里最考验“建模能力”的一章。前面学数组、链表、树的时候套路还相对固定——会遍历、会递归、会剪枝基本能应付但一进入 DP找零钱、最大连续子序列和、最长上升子序列、最长公共子序列、最长公共子串、0-1 背包六道经典题直接铺开每一道看起来都像新题。这章我花的时间比之前所有章节加起来都多反复手推状态转移表之后才慢慢建立起一套通用框架。这篇就把我整理好的动态规划六题笔记完整放出来。内容包括每道题的状态定义为什么这么写、转移方程怎么推、初始化边界踩过哪些坑、一维滚动数组优化何时该逆序以及最后的实操排查实录。适合刚学完基础数据结构、准备刷 DP 但总觉得“看答案会自己写就崩”的同学也适合想要一套可复用的 DP 解题模板去应对笔试的老手。1. 动态规划到底在干嘛先建立一套通用框架1.1 三个关键词状态、转移、边界动态规划处理的是“多阶段决策”问题一个大的决策过程可以被拆成很多重叠的小子问题每个小子问题的答案被保存下来后面直接复用。比如爬楼梯你不需要关心“我上一次是跨了一步还是两步”只需要关心“当前站在第几级台阶”。这句话听起来是废话但其实是 DP 最有价值的抽象状态里只保留对后续决策有影响的信息。一个 DP 解法的完整定义包含三件事。状态dp[i]代表什么转移dp[i]怎么由更小的状态算出边界最小的问题答案是多少拿斐波那契数列举例。状态是dp[n] 第 n 项转移是dp[n] dp[n-1] dp[n-2]边界是dp[0]0、dp[1]1。这三样一写出来代码就是照着抄的事。很多初学者栽在第一步“状态定义”上。状态定歪了后面转移和边界全跟着歪状态定好了题目基本就做完了。所以我把状态定义看得比写转移方程还重要每道题先逼自己把dp[i]是什么写清楚再想别的。1.2 拿到一道 DP 题的四个固定动作我自己总结的套路做任何 DP 题都先走这四步定义状态想清楚dp的每个维度表示什么是“前 i 个”还是“以 i 结尾”还是“容量为 j”维度有没有覆盖题目所有限制条件。写转移方程从“最后一步”倒推假设前面的状态都算好了当前状态怎么由它们组合出来。初始化边界把最小的、不用算就知道答案的状态填好把“非法状态”用一个特殊值表示。确定遍历顺序和答案位置是从左到右、从 1 到 n还是两层循环答案在dp[n]、dp[0]还是max(dp)这套流程里最容易翻车的是第 4 步。很多人状态、转移都对结果答案位置取错或者一维优化时遍历顺序写反白搞半天。后面每道题我都会把答案位置单独拎出来说。2. 一维数组上的第一课最大连续子序列和 / 最长上升子序列2.1 最大连续子序列和一个变量就能滚动题目给定一个整数数组nums找出一个具有最大和的连续子数组返回最大和。比如[-2,1,-3,4,-1,2,1,-5,4]答案是6对应子数组[4,-1,2,1]。先定状态。注意这里的关键是“连续”连续子数组一定要有一个右端点所以状态定义为dp[i] 以 nums[i] 结尾的连续子数组的最大和。为什么要“以 i 结尾”因为只有定死了结尾转移才说得清楚。当你知道dp[i-1]之后到nums[i]这一步只有两种可能要么把nums[i]接在以nums[i-1]结尾的那个最优子数组后面要么干脆不要前面的从nums[i]重新开始。于是转移方程dp[i] max(nums[i], dp[i-1] nums[i])这个方程的含义很直白dp[i-1]如果是负数接上它只会让nums[i]更小那就直接取nums[i]。手推一遍[-2,1,-3,4,-1,2,1,-5,4]inums[i]dp[i]说明0-2-2直接取自身111-21 1重新开始2-3-21(-3)-2344-242 4重新开始4-134(-1)35253256165167-516(-5)1845145答案不是dp[8]而是max(dp)也就是6。这一点很多人第一次都会记错因为“以某个位置结尾”的 dp 数组最大值不一定在最后一个位置。代码可以优化到一维滚动def max_subarray(nums): cur max_sum nums[0] for x in nums[1:]: cur max(x, cur x) max_sum max(max_sum, cur) return max_sum注意一个细节cur初始化为nums[0]不是0。如果数组全是负数初始化为 0 会把答案错误地算成 0实际上应该是最大的那个负数。这个坑我在面试白板题上踩过一次印象极深。2.2 最长上升子序列从“末尾”思考 O(n²) 与二分优化题目给定一个整数数组求最长严格递增子序列的长度。注意子序列不需要连续。比如[10,9,2,5,3,7,101,18]答案是4对应[2,3,7,101]或[2,5,7,101]。状态定义同样是“以 i 结尾”dp[i] 以 nums[i] 结尾的最长上升子序列长度。为什么不能定义成“前 i 个元素的最长上升子序列”因为子序列可以不连续只给“前 i 个”这个信息你不知道最后一个元素是什么也就没法判断续上去之后是否递增。所以必须把结尾钉死。转移时要往前找所有j i且nums[j] nums[i]的位置把dp[j] 1当作候选dp[i] max(dp[j] 1) 对所有 j i 且 nums[j] nums[i]手推[10,9,2,5,3,7,101,18]inums[i]dp[i]怎么来的0101初始19110 9无法接221接不上352接在 2 后面432接在 2 后面573接在 2→5 或 2→3 后面61014能接在之前任意一个后面7184接在 2→3→7 后面最终答案是max(dp)4。O(n²) 的代码不复杂但有些题目数据量大了会超时。优化思路是用tails数组配合二分tails[k]表示“长度为 k1 的上升子序列中末尾元素的最小值”。遍历每个x在tails里找第一个不小于x的位置并替换如果找不到说明x可以接在目前最长的序列后面直接追加。import bisect def length_of_lis(nums): tails [] for x in nums: i bisect.bisect_left(tails, x) if i len(tails): tails.append(x) else: tails[i] x return len(tails)一个必须理解的细节tails并不是真实子序列它只是贪心地记录“最小末尾”。举个例子[2,3,1]跑下来tails是[1,3]但[1,3]并不是原数组的子序列不影响长度计算。这一点面试时如果被追问能讲清楚会让对方刮目相看。2.3 一维 DP 的常见坑这两个题至少能总结出三个高频错误。初始化错误LIS 的dp数组初始化为全 1不是全 0。每个元素自身构成一个长度为 1 的子序列这是合法状态。答案位置错误这类“以 i 结尾”的状态答案往往要遍历取max不是直接输出dp[n-1]。子序列和子数组混淆连续子数组的转移是“要么接、要么重新开始”非连续子序列的转移是“往前扫找能接的位置”。判断清楚题目说的是“连续”还是“不连续”决定了整个解法方向。3. 二维 DP 双序列问题最长公共子序列 / 最长公共子串3.1 最长公共子序列看最后一个字符是否相等题目给定两个字符串text1、text2返回它们最长公共子序列的长度。子序列不要求连续但相对顺序要一致。比如abcde和aceLCS 是ace长度3。双序列问题最经典的状态定义是dp[i][j] text1 的前 i 个字符 与 text2 的前 j 个字符 的最长公共子序列长度注意这里用的是“前 i 个”不是“以第 i 个字符结尾”。原因和上一节一样子序列不连续强制“以某字符结尾”会丢掉中间跳过的可能性。转移的核心是看两个字符串的最后一位是否相等。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])相等时直接把这两个字符拼在“各自前一个字符的 LCS”后面不相等时说明这两个字符不可能同时出现在 LCS 末尾只能丢掉其中一个所以取“text1 少一个字符”和“text2 少一个字符”两种情况的最大值。手推text1abcde、text2acedp空ace空0000a0111b0111c0122d0122e0123答案是dp[5][3] 3就在右下角。二维 dp 表右下角天然就是“前 m 个和前 n 个”的结果位置不会搞错。代码def longest_common_subsequence(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]为什么 dp 表要开成(m1) x (n1)而不是m x n因为空串是最小边界。dp[0][j]表示空串和任意字符串的 LCS必然是 0dp[i][0]同理。这样天然规避了“下标越界”和“单独初始化第一行第一列”的麻烦。3.2 最长公共子串加一个连续性的条件题目对比 LCS 只在一点不同公共子串是连续的。比如abcde和cdaf最长公共子串是cd长度2而它们的 LCS 是cd或da长度也是2。但换一组数据就能看出差别比如abcdef和zabcdeLCS 是abcde长度 5而最长公共子串也是abcde长度 5看起来差不多但abcd和axbcd的 LCS 是abcd长度 4最长公共子串是bcd长度 3。状态定义必须改成dp[i][j] 以 text1[i-1] 和 text2[j-1] 这两个字符结尾的公共子串长度转移很干净if text1[i-1] text2[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] 0不相等就断掉置为 0。这正好保证了“连续”如果中间断了后续哪怕字符相等也只能从 1 重新累积。答案不是dp[m][n]而是整个 dp 表的max。因为公共子串不一定在原字符串的末尾结束最长的一段可能出现在中间任何位置。这个“答案位置不同”是最容易和 LCS 混淆的地方我专门记过一句子序列看右下子串扫全局。代码也可以把 dp 数组压缩成一维但要注意遍历方向def longest_common_substring(a, b): m, n len(a), len(b) dp [0] * (n 1) ans 0 for i in range(1, m 1): for j in range(n, 0, -1): if a[i-1] b[j-1]: dp[j] dp[j-1] 1 ans max(ans, dp[j]) else: dp[j] 0 return ansj必须从大到小。因为dp[j]依赖的是上一行、前一列的dp[j-1]。如果正序更新dp[j-1]可能已经被当前行覆盖算出来的就是当前行的值逻辑就错了。这个“逆序更新”和 0-1 背包的一维优化是同一个原理后面还会再见到。3.3 这两道题放在一起对比对比项最长公共子序列最长公共子串连续性不要求连续必须连续状态定义前 i 个与前 j 个以 i、j 结尾不相等时取两侧较大值直接归 0答案位置dp[m][n]全表 max一维化方向可用两行交替必须从右往左把这两个放在一起学比单独刷十道题还管用。因为状态定义的差异直接导致转移和答案位置的差异体会一次就能记住“为什么子串要断掉”。4. 带上“容量/金额”的重量维度0-1 背包与找零钱4.1 0-1 背包选或不选状态里多一维题目有 n 件物品每件物品有重量w[i]和价值v[i]背包容量为W每件物品最多选一次选或不选求能装下的最大价值。状态需要同时记录“看完了哪些物品”和“当前用了多少容量”所以是二维dp[i][j] 前 i 件物品在容量不超过 j 的条件下能获得的最大价值转移就是标准的“选/不选”二选一dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]) 当 j w[i]不选第 i 件价值和前 i-1 件一样选第 i 件得先给这件物品腾出w[i]的容量加上它的价值。这个“腾容量”的写法是所有背包类问题的灵魂。先写二维版本更容易理解def knapsack_01_2d(weights, values, capacity): n len(weights) dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(capacity 1): if j weights[i-1]: dp[i][j] max(dp[i-1][j], dp[i-1][j - weights[i-1]] values[i-1]) else: dp[i][j] dp[i-1][j] return dp[n][capacity]一维优化是面试考得最多的点。关键在于状态转移只用到了上一行的数据所以可以只留一个一维数组但要保证更新dp[j]时用的dp[j-w[i]]是“上一轮”的值。这就必须让容量从大到小遍历def knapsack_01_1d(weights, values, capacity): n len(weights) dp [0] * (capacity 1) for i in range(n): for j in range(capacity, weights[i] - 1, -1): dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[capacity]为什么逆序看一个反例。假设一件物品重量 1、价值 2背包容量 2。如果正序循环dp[1]先被更新成 2接着dp[2]会用到dp[1] 2 4相当于同一件物品被选了两次。而正常情况一件物品最多选一次dp[2]应该是 2。逆序时dp[2]先算它用的dp[1]还是上一轮的旧值 0结果正确。初始化也有讲究。如果题目要求“恰好装满背包”dp[0]0其余初始化为负无穷如果只是“不超过容量”求最大价值全部初始化为 0 就行。区别在于恰好装满时容量为 1 却根本没有物品能填满它应该是非法状态不能参与后续转移的候选。4.2 找零钱从“最少硬币数”看完全背包变体题目给定不同面额的硬币coins和一个总金额amount求凑出该金额所需的最少硬币数如果无法凑出返回 -1。硬币可以无限使用。状态定义天然是一维的dp[a] 凑出金额 a 所需的最少硬币数转移时最后一步一定是用一枚面额为coin的硬币来结束dp[a] min(dp[a - coin] 1) 对所有 a coin代码def coin_change(coins, amount): dp [amount 1] * (amount 1) dp[0] 0 for a in range(1, amount 1): for coin in coins: if a coin: dp[a] min(dp[a], dp[a - coin] 1) return dp[amount] if dp[amount] ! amount 1 else -1两个细节必须说透。初始值为什么是amount 1因为最坏情况下就算用面额为 1 的硬币凑amount也只需要amount枚。amount 1在这个题目里等于“不可能达到”的标记值而且这个标记必须是足够大的数不能是 0。如果初始化为 0min的时候会直接把 0 当作最优解传下去最后结果全变成 0。dp[0] 0是唯一的合法边界它表示“凑出 0 块钱需要 0 枚硬币”也是所有金额转移的起点。找零钱在背包问题上属于“完全背包”硬币可以无限使用。对比 0-1 背包的一维化这里金额循环要正序正序更新才能让同一个硬币被多次使用。如果换一种循环写法——先遍历硬币、再遍历金额——也能得到同样的结果for coin in coins: for a in range(coin, amount 1): dp[a] min(dp[a], dp[a - coin] 1)两种写法在“求最少硬币数”时都能得到正确答案但语义不同。先金额后硬币更像“站在金额角度思考最后一步”先硬币后金额更像“站在硬币角度考虑它能贡献给哪些金额”。4.3 如果题目换一种问法凑成目标金额有多少种方案这是检验你是否真正理解“遍历顺序”和“组合/排列”区别的好题。同样是coins[1,2]amount3。先遍历硬币外层 coin、内层金额得到的是组合数dp [0] * (amount 1) dp[0] 1 for coin in coins: for a in range(coin, amount 1): dp[a] dp[a - coin]结果是 2对应[1,1,1]和[1,2]。因为先固定硬币面额就相当于按“面额从小到大的顺序”选择硬币天然保证1不会出现在2之后不会产生[2,1]这种重复排列。先遍历金额外层金额、内层硬币得到的是排列数for a in range(1, amount 1): for coin in coins: if a coin: dp[a] dp[a - coin]结果是 3对应[1,1,1]、[1,2]、[2,1]。因为每一层金额都会考虑“最后一枚硬币是谁”1 和 2 的可能顺序都会被计入。这个扩展题非常值得自己动手跑一遍跑通了你对这两类循环的理解会上一个台阶。5. 六道题一张表状态定义、转移、答案位置与易错点5.1 六题速查表题目状态定义核心转移答案位置易错点最大连续子序列和dp[i]: 以 nums[i] 结尾的最大和max(nums[i], dp[i-1] nums[i])max(dp)初始化取 nums[0]最长上升子序列dp[i]: 以 nums[i] 结尾的 LIS 长度max(dp[j]1)ji 且 nums[j]nums[i]max(dp)初始化为 1最长公共子序列dp[i][j]: 前 i 个与前 j 个的 LCS相等 1否则取两侧 maxdp[m][n]dp 表偏移一位最长公共子串dp[i][j]: 以二者结尾的公共子串长度相等 1不等归 0全表 max答案不在右下角0-1 背包dp[i][j]: 前 i 件、容量 j 最大价值max(不选, 选value)dp[n][W]一维化后容量逆序找零钱最少硬币dp[a]: 凑出 a 最少硬币数min(dp[a-coin]1)dp[amount]初始化为大数这张表我每次刷题前都会扫一遍。六道题看似千差万别但本质都是同一套框架状态、转移、边界、答案位置。5.2 通用检查清单如果新题一眼没思路我能给你的实操建议是逐条过这个清单。状态里有没有覆盖“所有影响未来决策的信息”比如只记“前 i 个”却不知道最后一个数就无法判断递增所以 LIS 必须改成“以 i 结尾”。转移方程有没有环DP 要求后面的状态只能依赖前面算好的状态。如果出现 dp[i] 依赖 dp[i1] 又反过来依赖 dp[i]你就要重新思考遍历顺序。初始化为“半合法”还是“非法”背包的负无穷、找零钱的大数都是把“不可能”和“未计算”区分开的手段。答案在哪个位置文档里反复出现的max(dp)和dp[n]的差别是最容易丢分的地方。能不能滚动能用一维就用一维但先想清楚方向0-1 背包逆序、找零钱正序、最长公共子串逆序、LCS 两行交替各有原因。6. 实战排查实录几个我反复踩的坑与解决办法6.1 找零钱在 amount 很大时被判超时问题出在哪我第一版找零钱是这样写的每次都用min遍历所有硬币且没有排序剪枝。数据量大了之后有些分支跑得非常慢。后来做了两处调整。先把coins排序当coin a时直接跳出内层循环省掉大量无效判断。在递归解法里加记忆化把已经算过的金额存进字典避免重复递归。补充一句找零钱这道题不能用贪心。常见反例是coins[1,3,4]、amount6贪心会先用面值 4剩下 2 用 1需要 3 枚硬币最优解其实是[3,3]只要 2 枚。这个反例面试出现频率很高。6.2 求“具体方案”而不是“长度/数量”时怎么回溯如果题目要求输出具体子序列、子数组或选择的物品光靠 dp 值不够需要额外记录决策。LCS 回溯从右下角dp[m][n]往回走。若text1[i-1]text2[j-1]说明这个字符被选中了记录后向左上走若不相等则比较dp[i-1][j]和dp[i][j-1]往值较大的方向走。0-1 背包回溯在二维 dp 之外建一个choice[i][j]记录容量 j 下是否选择了第 i 件物品。最后从dp[n][W]反向推出装的是哪些。找零钱回溯增加last[a]记录凑出金额 a 时最后用的硬币面额。从last[amount]一路往回减就能还原整套方案。回溯不是 DP 的标配但面试问“能不能打印方案”时没准备的人容易手忙脚乱。提前把这三个写法捋一遍现场只是复制粘贴改改。6.3 滚动数组方向总写反怎么办我总结了一个记忆口诀依赖旧值逆序更新依赖新值正序更新。0-1 背包一维化时dp[j]需要的是dp[j-w[i]]必须来自上一轮循环所以容量逆序。找零钱中硬币可复用我们希望后算的金额能用到刚更新过的旧值相当于同一硬币用多次所以金额正序。最长公共子串一维化时dp[j]依赖左上角的dp[j-1]如果正序那个位置的旧值会被当前行覆盖所以也要逆序。写代码之前先问一句我这行的dp[...]是来自上一轮还是本轮这个问题想清楚方向就不会错。6.4 笔试 10 分钟快速复习版进笔试前如果时间紧张只看这几条就够。看到“子序列、子数组、背包、凑钱、路径计数”这些关键词先往 DP 上想。写转移方程前先把状态定义写成注释放在代码第一行防止写着写着把 dp 的含义带偏。初始化默认值时问自己这个默认值代表合法解还是非法解找零钱的amount1、背包的-inf都是非法标记。写完代码用一个小例子手动跑一遍二维表不要只跑套测试数据。手动跑表的五分钟能救回很多只有提交才暴露的边界错误。结尾动态规划这章我最开始完全靠背模板换一道题就发懵。后来把找零钱、最大连续子序列和、最长上升子序列、最长公共子序列、最长公共子串、0-1 背包放在一起逐行对比才真正醒悟状态定义写对了转移方程就是水到渠成的事后面的初始化、遍历顺序、答案位置全是围绕“状态定义”转的。尤其是找零钱那个dp[0]0、其他初始化为大数的细节我当初怎么都想不通。直到我把金额从 1 到 amount 全部打印出来一个个对着看才知道大数是为了把“凑不够”和“还没算”区分开。这种笨办法看着慢实际比盲刷十道新题都扎实。希望这份笔记能让你少走几步弯路更希望你能自己去手推一遍 dp 表——那个过程才是真正把动态规划变成自己能力的过程。