准备算法面试的同学应该都有这种经历一看到题目里带“动态规划”四个字脑子先嗡一下。状态怎么定义转移方程怎么写为什么别人能想到我只能对着样例发呆这太正常了动态规划本来就比其他算法题更吃经验和感觉。今天这篇就来聊经典动态规划的第一部分把最基础、最高频的板子全部掰开揉碎讲清楚包括一维DP、二维DP、背包问题和序列型DP的典型代表把这些吃透了后面再遇到难题才有底气往深处想。这篇内容适合正在刷题准备校招、社招的同学也适合那些已经刷了一些题但总是卡在“状态转移方程”这一步的人。我会从最底层的思想讲起配合代码、例子、踩坑记录尽量把“为什么这么想”讲透而不是只丢一个答案出来。我相信你看完这篇至少能把动态规划大类的常见套路理顺遇到新题也不会像无头苍蝇一样乱转。1. 动态规划到底在干什么先把这个底层逻辑吃透1.1 递归重复计算的痛点就是动态规划的解药理解动态规划最好的方式是先从它的反面入手。很多新手拿到动态规划题的时候第一反应会尝试用递归去解。递归本身没问题问题在于直接递归往往伴随大量重复计算。拿最经典的斐波那契数列来说f(n) f(n-1) f(n-2)你如果直接写递归int fib(int n) { if (n 1) return n; return fib(n - 1) fib(n - 2); }这个函数跑fib(50)在普通机器上基本就卡死了。原因在于它把fib(40)、fib(30)这些子问题反复计算了无数次。你可以试着手工展开一下fib(10)的递归树会发现同样一个节点被访问了非常多遍。动态规划的思路就是反过来既然子问题会被重复使用那我干脆把每个子问题的答案都记下来用数组存好从最小的子问题开始一步一步往上推。这就是所谓的“自底向上”求解。这个思想本质上和用缓存去优化递归是一回事只是DP通常优化得更系统、更高效。所以你记住一句话动态规划不是玄学它是“带记忆的递归”是拿空间换时间。1.2 最优子结构为什么拆成子问题是对的搞清楚了重复计算第二个关键问题是什么样的问题才能用动态规划答案很简单两个条件一是重叠子问题上一节已经说过二是最优子结构。所谓最优子结构就是整个问题的最优解可以由子问题的最优解推导出来。我举个例子。假设你想从北京去上海中间经过南京。如果你知道“北京到南京”的最优路线和“南京到上海”的最优路线那把这两段拼起来理论上就是“北京到上海”的最优路线。这个问题的子问题之间没有相互影响各自独立拼接起来就是整体最优这就是最优子结构。反之如果一个问题的子问题之间有复杂的耦合关系比如叫“全局最优需要牺牲某个局部最优点”的那种问题动态规划可能就不太适用了或者需要加额外的状态维度来处理。1.3 贪心、分治、动态规划三者到底什么关系面试中经常被顺带问到“贪心和动态规划有什么区别”这里也一并解释清楚。贪心算法是每一步都做当前看起来最优的选择希望最后全局最优。它的优点是效率高但缺点很明显太短视了一旦局部最优推不出全局最优就直接翻车。而动态规划则考虑更加全面它会同时维护多个候选状态最后通过转移方程取最优解理论上可以得到全局最优。分治算法和动态规划都涉及把问题拆成子问题但分治的典型场景是子问题之间相互独立不存在重叠比如归并排序而动态规划的子问题往往有大量重叠所以才需要“记忆化”来避免重复计算。我打过一个比方贪心像是一个只顾低头往前走的人每次走最近的一步动态规划像是一个拿着地图的人每到一个岔路口把所有路线都走一遍、把结果记下来最后再挑最短的那条。三者没有谁绝对好关键看问题适用不适用。你把这个区别讲清楚了面试官对你好感度会明显上升。2. 从斐波那契到不同路径三种递推模型带你上手2.1 一维DP斐波那契数列与爬楼梯动态规划入门几乎所有人都是从一维DP开始的。所谓一维DP就是状态只需要一个维度就能描述清楚比如“走到第 i 级台阶有几种走法”。我们来看一道面试常考题爬楼梯。假设你正在爬楼梯楼梯有 n 级每次可以爬 1 级或 2 级问有多少种不同的方法爬到楼顶这个问题的状态定义非常直接设dp[i]表示到达第 i 级台阶的方法总数。那么想一下你站在第 i 级台阶上一步可能是从第 i-1 级爬上来的也可能是从第 i-2 级直接跳上来的。所以状态转移方程就是dp[i] dp[i-1] dp[i-2]初始化条件是dp[1] 1只有一种方式爬1级dp[2] 2可以11也可以直接2。然后从 i3 一直算到 n就得到答案了。这个问题看起来和斐波那契数列几乎一模一样但面试官喜欢在这里加各种变形比如“每次可以爬1级、2级或3级”那转移方程就变成dp[i] dp[i-1] dp[i-2] dp[i-3]或者“爬楼梯时不能连续爬2级”那就要增加一个状态维度来记录上一次是爬了几级。你要能从基础版推导到变形版才算真掌握。2.2 二维DP不同路径问题一维DP的思路一旦通了二维DP其实就是多了一个状态维度思考方式完全一样。我们看 LeetCode 上那道“不同路径”一个机器人位于 m x n 网格的左上角每次只能向下或者向右移动一步问到达右下角总共有多少条不同的路径。状态定义dp[i][j]表示从起点到达网格中第 i 行第 j 列这个位置的路径总数。因为机器人只能向右和向下走所以想到达(i, j)只能从上面的格子(i-1, j)或者左边的格子(i, j-1)走过来。于是状态转移方程就是dp[i][j] dp[i-1][j] dp[i][j-1]初始化第一行和第一列的格子都只有一种走法一直向右或者一直向下所以都置为 1。这个题说难吗不难但它特别能检验你对二维状态的掌握程度。面试时我建议你先把状态定义说出来再手写转移方程最后再补代码。这个顺序本身就是一种解题套路。2.3 状态设计的关键你觉得一维不够用就升维我发现很多同学在做DP题时最难的就是“设计状态”这一步。面对一个题目怎么知道用一维还是二维怎么知道每个维度代表什么这里有个比较实用的经验先看题目的约束条件里有哪些关键变量。比如爬楼梯的变量只有“楼层数”那大概率是一维DP不同路径的变量是“行和列”两个值那大概率是二维DP如果题目又说“每个格子走过以后不能再走”那你可能还要额外加一个维度来表示访问状态这就变成状态压缩DP了不过那是后话。说白了状态里的每一个维度都要对应一个影响后续决策的因素。当一个因素会影响你下一步怎么选但又无法从当前值里推断出来的时候就必须把这个因素作为状态的一部分记录下来。这个“升维”的思路是解决所有动态规划难题的核心钥匙。3. 背包问题面试中最高频的动态规划模型3.1 01背包每个物品只有拿和不拿两种状态背包问题特别是01背包绝对是动态规划面试里的顶流。我统计过十场算法面试里至少有三场会聊到背包或者加一道背包的变形题。先看最标准的01背包题目描述有一个背包容量为 V现在有 N 个物品第 i 个物品的体积为 weight[i]价值为 value[i]每个物品只能被选一次问背包能装下的最大价值是多少状态定义dp[i][j]表示把前 i 个物品放入容量为 j 的背包中能够获得的最大价值。然后我们来想转移方程。对于第 i 个物品你有两个选择不拿它那dp[i][j] dp[i-1][j]拿它那需要保证背包有足够的容量此时dp[i][j] dp[i-1][j - weight[i]] value[i]。两者取最大值所以dp[i][j] max(dp[i-1][j], dp[i-1][j - weight[i]] value[i])举个例子。假设背包容量 V5有三个物品体积分别是 1、2、3价值分别是 6、10、12。初始化二维表全部是0然后逐行填充最后dp[3][5]就是最大价值。实际写代码时很多人会习惯用一维数组滚动优化后面我会详细讲但初次学习一定要先理解二维表的填充过程否则直接上优化版本很容易懵。3.2 完全背包与遍历顺序的坑01背包搞懂后完全背包就来了。完全背包和01背包的唯一区别是每个物品可以选择无限次。题目描述通常变成“第 i 种物品可以取任意多件”。这个“无限次”听起来只改了一个字但实现上有一个特别容易踩的坑内层循环的遍历顺序。01背包的优化版代码内层容量 j 是从大到小遍历的for (int i 0; i N; i) { for (int j V; j weight[i]; j--) { dp[j] max(dp[j], dp[j - weight[i]] value[i]); } }为什么要从大到小因为我们要保证第 i 个物品只被选一次。如果正序遍历dp[j - weight[i]] 可能已经是更新过、包含了第 i 个物品的状态这样 dp[j] 就可能把一个物品重复算进去那就不叫01背包了。但完全背包恰恰需要这种“重复选同一个物品”的效果所以它的容量遍历顺序是正序的for (int i 0; i N; i) { for (int j weight[i]; j V; j) { dp[j] max(dp[j], dp[j - weight[i]] value[i]); } }这里就出现了一个面试高频考点为什么01背包的容量要倒序遍历完全背包要正序遍历你如果能在面试现场把这个问题讲明白面试官基本就能确定你是真的理解了背包DP的底层逻辑而不是背模板。3.3 背包问题的初始化技巧与变形题背包问题的进阶考点藏在“初始化”里。最常见的两种初始化方式如果题目要求“恰好装满背包”那么dp[0] 0其余容量初始化为负无穷比如-0x3f3f3f3f因为只有容量为0时才是合法状态其他容量表示“还没凑出来”。如果题目只要求“最大价值”没有“恰好装满”的条件那所有位置都可以初始化为0表示什么都不装也有价值0。这个区别容易被忽略但实际面试中经常出现。我见过不止一个候选人代码写得挺顺结果初始化给错了导致整个答案不对。背包题还有一个非常常见的变形叫“分组背包”把物品分组每组只能选一个这种题的核心思路是在原来的01背包外层再加一层组循环。另外还有“多重背包”每种物品有一个数量上限需要用到二进制拆分优化。把这些都整理一遍背包这块就算吃得比较透了。4. 序列型DPLIS、LCS、编辑距离三大代表4.1 最长递增子序列LIS双循环的经典写法如果说背包是背包DP的代表那序列型DP就是另一个大类。序列型DP解决的是和数组、字符串相关的子序列问题。面试中见最多的就是最长递增子序列LIS、最长公共子序列LCS、编辑距离。这里逐个说。LIS的题目描述给定一个无序的整数数组找到其中最长严格递增子序列的长度。状态定义dp[i]表示以第 i 个元素结尾的最长递增子序列的长度。注意这里的“以 i 结尾”非常关键这保证了你把第 i 个元素加入子序列时前面的元素必须是小于 nums[i] 的。转移方程dp[i] max(dp[i], dp[j] 1), 其中 j i 且 nums[j] nums[i]也就是说遍历所有在 i 前面的元素如果 nums[j] nums[i]那说明 nums[i] 可以接在以 j 结尾的递增序列后面长度就是 dp[j] 1取最大值。代码写出来大概是这样int lengthOfLIS(vectorint nums) { int n nums.size(); vectorint dp(n, 1); int ans 1; for (int i 1; 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 log n)”这时候就需要用到贪心 二分查找的思路维护一个堆数组把问题转化为在堆数组中二分查找第一个比当前数大的位置。这种优化面试也是常客但属于进阶内容先把基础DP理解到位再说。4.2 最长公共子序列LCS二维表的填充逻辑LCS题目描述给定两个字符串 text1 和 text2返回这两个字符串的最长公共子序列的长度。状态定义dp[i][j]表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列长度。这里用“前 i 个”而不是“以 i 结尾”是一种常见但容易混淆的状态定义方式需要特别注意。转移方程分两种情况如果text1[i-1] text2[j-1]说明当前字符可以匹配那么dp[i][j] dp[i-1][j-1] 1如果不相等那就只能从两个可能中取较大值dp[i][j] max(dp[i-1][j], dp[i][j-1])。初始化dp[0][j]和dp[i][0]都为0表示任一字符串为空时公共子序列长度都是0。我建议你手工填一次这个二维表比如text1 abcde、text2 ace逐行逐列去推你会很快体会到这里面“偷懒”的精髓当前字符不相同时我们不强行匹配而是继承前面已经算好的较大值。4.3 编辑距离把问题拆成插入、删除、替换编辑距离是序列型DP里硬核度比较高的一道题也是经典面试题。题目是给你两个单词 word1 和 word2你可以对一个单词进行插入、删除、替换三种操作请返回将 word1 转换成 word2 所使用的最少操作数。状态定义dp[i][j]表示 word1 的前 i 个字符转换成 word2 的前 j 个字符所需要的最少操作数。转移方程比前面复杂一些但逻辑清晰。我们看 word1[i-1] 和 word2[j-1]如果相等dp[i][j] dp[i-1][j-1]不需要额外操作如果不等有三种操作选择插入在 word1 中插入一个字符让它跟 word2[j-1] 匹配操作数为dp[i][j-1] 1删除把 word1[i-1] 删掉操作数为dp[i-1][j] 1替换把 word1[i-1] 替换成 word2[j-1]操作数为dp[i-1][j-1] 1。然后取三个值的最小值dp[i][j] min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) 1初始化时需要注意dp[i][0] i表示把 word1 的前 i 个字符全部删掉dp[0][j] j表示把空串插入 j 个字符变成 word2 的前 j 个字符。这两个边界只要错一个整个答案就错。这道题虽然是 hard 难度但你一旦把“插入、删除、替换”三个操作对应到状态转移的三种来源它其实比很多中等题还要顺。5. 面试实战动态规划解题五步法5.1 第一步到第三步定义状态、列转移方程、初始化刷了很多DP题之后我自己总结了一套解题流程按这个流程走哪怕最后没做出来面试官也会觉得你思路在正轨上。第一步定义状态。这是最核心的一步用一句话说清楚dp[i]或dp[i][j]表示什么。命名要清晰比如dp[i]表示“以第 i 个元素结尾的最大子数组和”而不是笼统地说“前 i 个元素的最大值”。第二步写状态转移方程。这一步通常对应的是“最后一步怎么做”。你想一想在最优策略里面最后一步可能是怎么发生的然后倒推它和上一步之间的关系。比如爬楼梯最后一步要么是爬1级要么是爬2级所以转移方程就分成两支相加。这一步想通了把方程写出来题目就完成了一大半。第三步确定初始化条件。初始化往往和状态定义里的“空”或者“边界”有关。比如空数组、空字符串、容量为0、走到网格的第一行第一列这些特殊情况的值是什么必须先定下来。5.2 第四步到第五步确认遍历顺序再谈空间优化第四步确定遍历顺序。你要搞清楚计算dp[i]的时候它依赖的dp[i-1]或dp[i-2]是否已经算好了。如果依赖的是上一轮的值你可能需要逆序遍历如果依赖的是本轮的已算值则可以正序遍历。这也就是01背包和完全背包遍历顺序不同的根本原因。第五步空间优化。DP很多情况下可以压缩空间。比如二维dp[i][j]如果只依赖上一行dp[i-1][...]的数据就可以把二维数组压成一行一维数组然后从后往前更新如果依赖的是左上角的数据那还需要用一个单独的变量记住被覆盖的旧值。空间优化不是必须的但面试时主动提出来会显得你理解更深。5.3 空间优化从二维压到一维的通用手法这里把空间优化单独拎出来讲因为它是一个高频考点而且很多初学者会在优化后完全看不懂代码。以01背包为例原始的二维表dp[i][j]只依赖上一行dp[i-1][j]和dp[i-1][j - weight[i]]。换句话说我们只需要保留前一行就能计算出当前行。既然如此为什么不用一行数组反复覆盖呢关键在于必须从后往前更新。因为如果从左往右更新dp[j - weight[i]]可能已经在当前物品上被更新过了这样就会把一个物品用多次。倒序更新dp[j - weight[i]]还是上一轮的值正好符合01背包的语义。再比如LCS的二维表虽然dp[i][j]只依赖左上角、上方、左方三个位置的值但压缩成一维时左上方那个值会被覆盖掉所以你需要用一个prev变量单独记录。这是很多人在空间优化时最容易犯错的地方建议实际写一写对比一下。6. 常见问题与调试技巧刷动态规划踩过的坑6.1 边界条件与数组越界的排查动态规划题目的代码量不大但出错的概率特别高一个常见的原因就是边界条件。我见过最多的问题是数组下标从 0 开始但状态定义用的是“前 i 个”导致 array[i-1] 和 dp[i] 差一位结果一写就错位。建议在做题时先在纸上写清楚“dp[i]中的 i 到底表示前 i 个数还是以下标 i 结尾的数”这两种定义方式对应代码里完全不同的索引写法。另一个问题是数组越界。比如01背包的容量循环里如果weight[i]比背包容量还大那么dp[j - weight[i]]就会越界。解决办法是循环条件写成j weight[i]或者先判断j weight[i]再更新。虽然是小细节但本地编译不报越界面试写代码时却容易被面试官一眼指出来。6.2 状态转移方程写错时的自检方法如果你发现答案不对但代码又看不出明显毛病不要干瞪眼按这个顺序排查。先打印中间结果。把dp数组的每一轮值都输出出来对照手算、脑算的结果很快就能定位到是转移方程写错还是初始化错了。再用小样例验证。用规模很小的输入比如 n3、V5手工把二维表填一遍和代码运行结果对比哪个格子不对改哪个。这个方法笨但非常有效能解决百分之九十以上的DP调试问题。最后检查“最后一个维度”。比如你定义dp[i][j]表示前 i 个物品和前 j 天的情况但转移的时候是否把 i 和 j 的顺序搞混了这种错位经常发生在代码缩写的变量名里一旦看错真的很难发现。6.3 遇到DP题没思路时的破局顺序最后分享一个我刷题时常用的“破局顺序”遇到陌生的动态规划题按这个顺序往下走基本都能找到切入点。第一先看数据范围。如果 n 很小比如 n 20可以考虑状态压缩如果 n 在 10^5 级别大概率是 O(n log n) 的DP优化如果 n 在 10^3 级别那 O(n^2) 的DP大概率可以接受。数据范围会强烈暗示你该用什么量级的解法。第二尝试用暴力搜索的递归思路去解然后观察递归参数里有几个变量。递归函数里的参数基本就是把dp数组的几个维度。比如递归函数是dfs(i, j)那dp[i][j]就八九不离十。第三如果递归思路也能走通再把递归改成递推把递归出口转成初始化条件递归调用转成状态转移方程这样即使你一开始想不到标准DP解也能从暴力搜索演化出正确解法。面试中这个方法特别实用。动态规划的学习不是一蹴而就的我自己也是从一看到DP题就头疼到后来慢慢有能力把每个状态、每个方程讲清楚。这个过程最关键的就是多总结多归类把每道题的“状态定义”和“状态转移”拆出来反复琢磨。等你刷到一定量你会发现动态规划其实就那么几个套路一维线性、二维表格、背包、区间、树形。今天这篇把前三种讲透了后面的内容我们再慢慢深入。
动态规划入门：从一维DP到背包问题的核心套路详解
准备算法面试的同学应该都有这种经历一看到题目里带“动态规划”四个字脑子先嗡一下。状态怎么定义转移方程怎么写为什么别人能想到我只能对着样例发呆这太正常了动态规划本来就比其他算法题更吃经验和感觉。今天这篇就来聊经典动态规划的第一部分把最基础、最高频的板子全部掰开揉碎讲清楚包括一维DP、二维DP、背包问题和序列型DP的典型代表把这些吃透了后面再遇到难题才有底气往深处想。这篇内容适合正在刷题准备校招、社招的同学也适合那些已经刷了一些题但总是卡在“状态转移方程”这一步的人。我会从最底层的思想讲起配合代码、例子、踩坑记录尽量把“为什么这么想”讲透而不是只丢一个答案出来。我相信你看完这篇至少能把动态规划大类的常见套路理顺遇到新题也不会像无头苍蝇一样乱转。1. 动态规划到底在干什么先把这个底层逻辑吃透1.1 递归重复计算的痛点就是动态规划的解药理解动态规划最好的方式是先从它的反面入手。很多新手拿到动态规划题的时候第一反应会尝试用递归去解。递归本身没问题问题在于直接递归往往伴随大量重复计算。拿最经典的斐波那契数列来说f(n) f(n-1) f(n-2)你如果直接写递归int fib(int n) { if (n 1) return n; return fib(n - 1) fib(n - 2); }这个函数跑fib(50)在普通机器上基本就卡死了。原因在于它把fib(40)、fib(30)这些子问题反复计算了无数次。你可以试着手工展开一下fib(10)的递归树会发现同样一个节点被访问了非常多遍。动态规划的思路就是反过来既然子问题会被重复使用那我干脆把每个子问题的答案都记下来用数组存好从最小的子问题开始一步一步往上推。这就是所谓的“自底向上”求解。这个思想本质上和用缓存去优化递归是一回事只是DP通常优化得更系统、更高效。所以你记住一句话动态规划不是玄学它是“带记忆的递归”是拿空间换时间。1.2 最优子结构为什么拆成子问题是对的搞清楚了重复计算第二个关键问题是什么样的问题才能用动态规划答案很简单两个条件一是重叠子问题上一节已经说过二是最优子结构。所谓最优子结构就是整个问题的最优解可以由子问题的最优解推导出来。我举个例子。假设你想从北京去上海中间经过南京。如果你知道“北京到南京”的最优路线和“南京到上海”的最优路线那把这两段拼起来理论上就是“北京到上海”的最优路线。这个问题的子问题之间没有相互影响各自独立拼接起来就是整体最优这就是最优子结构。反之如果一个问题的子问题之间有复杂的耦合关系比如叫“全局最优需要牺牲某个局部最优点”的那种问题动态规划可能就不太适用了或者需要加额外的状态维度来处理。1.3 贪心、分治、动态规划三者到底什么关系面试中经常被顺带问到“贪心和动态规划有什么区别”这里也一并解释清楚。贪心算法是每一步都做当前看起来最优的选择希望最后全局最优。它的优点是效率高但缺点很明显太短视了一旦局部最优推不出全局最优就直接翻车。而动态规划则考虑更加全面它会同时维护多个候选状态最后通过转移方程取最优解理论上可以得到全局最优。分治算法和动态规划都涉及把问题拆成子问题但分治的典型场景是子问题之间相互独立不存在重叠比如归并排序而动态规划的子问题往往有大量重叠所以才需要“记忆化”来避免重复计算。我打过一个比方贪心像是一个只顾低头往前走的人每次走最近的一步动态规划像是一个拿着地图的人每到一个岔路口把所有路线都走一遍、把结果记下来最后再挑最短的那条。三者没有谁绝对好关键看问题适用不适用。你把这个区别讲清楚了面试官对你好感度会明显上升。2. 从斐波那契到不同路径三种递推模型带你上手2.1 一维DP斐波那契数列与爬楼梯动态规划入门几乎所有人都是从一维DP开始的。所谓一维DP就是状态只需要一个维度就能描述清楚比如“走到第 i 级台阶有几种走法”。我们来看一道面试常考题爬楼梯。假设你正在爬楼梯楼梯有 n 级每次可以爬 1 级或 2 级问有多少种不同的方法爬到楼顶这个问题的状态定义非常直接设dp[i]表示到达第 i 级台阶的方法总数。那么想一下你站在第 i 级台阶上一步可能是从第 i-1 级爬上来的也可能是从第 i-2 级直接跳上来的。所以状态转移方程就是dp[i] dp[i-1] dp[i-2]初始化条件是dp[1] 1只有一种方式爬1级dp[2] 2可以11也可以直接2。然后从 i3 一直算到 n就得到答案了。这个问题看起来和斐波那契数列几乎一模一样但面试官喜欢在这里加各种变形比如“每次可以爬1级、2级或3级”那转移方程就变成dp[i] dp[i-1] dp[i-2] dp[i-3]或者“爬楼梯时不能连续爬2级”那就要增加一个状态维度来记录上一次是爬了几级。你要能从基础版推导到变形版才算真掌握。2.2 二维DP不同路径问题一维DP的思路一旦通了二维DP其实就是多了一个状态维度思考方式完全一样。我们看 LeetCode 上那道“不同路径”一个机器人位于 m x n 网格的左上角每次只能向下或者向右移动一步问到达右下角总共有多少条不同的路径。状态定义dp[i][j]表示从起点到达网格中第 i 行第 j 列这个位置的路径总数。因为机器人只能向右和向下走所以想到达(i, j)只能从上面的格子(i-1, j)或者左边的格子(i, j-1)走过来。于是状态转移方程就是dp[i][j] dp[i-1][j] dp[i][j-1]初始化第一行和第一列的格子都只有一种走法一直向右或者一直向下所以都置为 1。这个题说难吗不难但它特别能检验你对二维状态的掌握程度。面试时我建议你先把状态定义说出来再手写转移方程最后再补代码。这个顺序本身就是一种解题套路。2.3 状态设计的关键你觉得一维不够用就升维我发现很多同学在做DP题时最难的就是“设计状态”这一步。面对一个题目怎么知道用一维还是二维怎么知道每个维度代表什么这里有个比较实用的经验先看题目的约束条件里有哪些关键变量。比如爬楼梯的变量只有“楼层数”那大概率是一维DP不同路径的变量是“行和列”两个值那大概率是二维DP如果题目又说“每个格子走过以后不能再走”那你可能还要额外加一个维度来表示访问状态这就变成状态压缩DP了不过那是后话。说白了状态里的每一个维度都要对应一个影响后续决策的因素。当一个因素会影响你下一步怎么选但又无法从当前值里推断出来的时候就必须把这个因素作为状态的一部分记录下来。这个“升维”的思路是解决所有动态规划难题的核心钥匙。3. 背包问题面试中最高频的动态规划模型3.1 01背包每个物品只有拿和不拿两种状态背包问题特别是01背包绝对是动态规划面试里的顶流。我统计过十场算法面试里至少有三场会聊到背包或者加一道背包的变形题。先看最标准的01背包题目描述有一个背包容量为 V现在有 N 个物品第 i 个物品的体积为 weight[i]价值为 value[i]每个物品只能被选一次问背包能装下的最大价值是多少状态定义dp[i][j]表示把前 i 个物品放入容量为 j 的背包中能够获得的最大价值。然后我们来想转移方程。对于第 i 个物品你有两个选择不拿它那dp[i][j] dp[i-1][j]拿它那需要保证背包有足够的容量此时dp[i][j] dp[i-1][j - weight[i]] value[i]。两者取最大值所以dp[i][j] max(dp[i-1][j], dp[i-1][j - weight[i]] value[i])举个例子。假设背包容量 V5有三个物品体积分别是 1、2、3价值分别是 6、10、12。初始化二维表全部是0然后逐行填充最后dp[3][5]就是最大价值。实际写代码时很多人会习惯用一维数组滚动优化后面我会详细讲但初次学习一定要先理解二维表的填充过程否则直接上优化版本很容易懵。3.2 完全背包与遍历顺序的坑01背包搞懂后完全背包就来了。完全背包和01背包的唯一区别是每个物品可以选择无限次。题目描述通常变成“第 i 种物品可以取任意多件”。这个“无限次”听起来只改了一个字但实现上有一个特别容易踩的坑内层循环的遍历顺序。01背包的优化版代码内层容量 j 是从大到小遍历的for (int i 0; i N; i) { for (int j V; j weight[i]; j--) { dp[j] max(dp[j], dp[j - weight[i]] value[i]); } }为什么要从大到小因为我们要保证第 i 个物品只被选一次。如果正序遍历dp[j - weight[i]] 可能已经是更新过、包含了第 i 个物品的状态这样 dp[j] 就可能把一个物品重复算进去那就不叫01背包了。但完全背包恰恰需要这种“重复选同一个物品”的效果所以它的容量遍历顺序是正序的for (int i 0; i N; i) { for (int j weight[i]; j V; j) { dp[j] max(dp[j], dp[j - weight[i]] value[i]); } }这里就出现了一个面试高频考点为什么01背包的容量要倒序遍历完全背包要正序遍历你如果能在面试现场把这个问题讲明白面试官基本就能确定你是真的理解了背包DP的底层逻辑而不是背模板。3.3 背包问题的初始化技巧与变形题背包问题的进阶考点藏在“初始化”里。最常见的两种初始化方式如果题目要求“恰好装满背包”那么dp[0] 0其余容量初始化为负无穷比如-0x3f3f3f3f因为只有容量为0时才是合法状态其他容量表示“还没凑出来”。如果题目只要求“最大价值”没有“恰好装满”的条件那所有位置都可以初始化为0表示什么都不装也有价值0。这个区别容易被忽略但实际面试中经常出现。我见过不止一个候选人代码写得挺顺结果初始化给错了导致整个答案不对。背包题还有一个非常常见的变形叫“分组背包”把物品分组每组只能选一个这种题的核心思路是在原来的01背包外层再加一层组循环。另外还有“多重背包”每种物品有一个数量上限需要用到二进制拆分优化。把这些都整理一遍背包这块就算吃得比较透了。4. 序列型DPLIS、LCS、编辑距离三大代表4.1 最长递增子序列LIS双循环的经典写法如果说背包是背包DP的代表那序列型DP就是另一个大类。序列型DP解决的是和数组、字符串相关的子序列问题。面试中见最多的就是最长递增子序列LIS、最长公共子序列LCS、编辑距离。这里逐个说。LIS的题目描述给定一个无序的整数数组找到其中最长严格递增子序列的长度。状态定义dp[i]表示以第 i 个元素结尾的最长递增子序列的长度。注意这里的“以 i 结尾”非常关键这保证了你把第 i 个元素加入子序列时前面的元素必须是小于 nums[i] 的。转移方程dp[i] max(dp[i], dp[j] 1), 其中 j i 且 nums[j] nums[i]也就是说遍历所有在 i 前面的元素如果 nums[j] nums[i]那说明 nums[i] 可以接在以 j 结尾的递增序列后面长度就是 dp[j] 1取最大值。代码写出来大概是这样int lengthOfLIS(vectorint nums) { int n nums.size(); vectorint dp(n, 1); int ans 1; for (int i 1; 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 log n)”这时候就需要用到贪心 二分查找的思路维护一个堆数组把问题转化为在堆数组中二分查找第一个比当前数大的位置。这种优化面试也是常客但属于进阶内容先把基础DP理解到位再说。4.2 最长公共子序列LCS二维表的填充逻辑LCS题目描述给定两个字符串 text1 和 text2返回这两个字符串的最长公共子序列的长度。状态定义dp[i][j]表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列长度。这里用“前 i 个”而不是“以 i 结尾”是一种常见但容易混淆的状态定义方式需要特别注意。转移方程分两种情况如果text1[i-1] text2[j-1]说明当前字符可以匹配那么dp[i][j] dp[i-1][j-1] 1如果不相等那就只能从两个可能中取较大值dp[i][j] max(dp[i-1][j], dp[i][j-1])。初始化dp[0][j]和dp[i][0]都为0表示任一字符串为空时公共子序列长度都是0。我建议你手工填一次这个二维表比如text1 abcde、text2 ace逐行逐列去推你会很快体会到这里面“偷懒”的精髓当前字符不相同时我们不强行匹配而是继承前面已经算好的较大值。4.3 编辑距离把问题拆成插入、删除、替换编辑距离是序列型DP里硬核度比较高的一道题也是经典面试题。题目是给你两个单词 word1 和 word2你可以对一个单词进行插入、删除、替换三种操作请返回将 word1 转换成 word2 所使用的最少操作数。状态定义dp[i][j]表示 word1 的前 i 个字符转换成 word2 的前 j 个字符所需要的最少操作数。转移方程比前面复杂一些但逻辑清晰。我们看 word1[i-1] 和 word2[j-1]如果相等dp[i][j] dp[i-1][j-1]不需要额外操作如果不等有三种操作选择插入在 word1 中插入一个字符让它跟 word2[j-1] 匹配操作数为dp[i][j-1] 1删除把 word1[i-1] 删掉操作数为dp[i-1][j] 1替换把 word1[i-1] 替换成 word2[j-1]操作数为dp[i-1][j-1] 1。然后取三个值的最小值dp[i][j] min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) 1初始化时需要注意dp[i][0] i表示把 word1 的前 i 个字符全部删掉dp[0][j] j表示把空串插入 j 个字符变成 word2 的前 j 个字符。这两个边界只要错一个整个答案就错。这道题虽然是 hard 难度但你一旦把“插入、删除、替换”三个操作对应到状态转移的三种来源它其实比很多中等题还要顺。5. 面试实战动态规划解题五步法5.1 第一步到第三步定义状态、列转移方程、初始化刷了很多DP题之后我自己总结了一套解题流程按这个流程走哪怕最后没做出来面试官也会觉得你思路在正轨上。第一步定义状态。这是最核心的一步用一句话说清楚dp[i]或dp[i][j]表示什么。命名要清晰比如dp[i]表示“以第 i 个元素结尾的最大子数组和”而不是笼统地说“前 i 个元素的最大值”。第二步写状态转移方程。这一步通常对应的是“最后一步怎么做”。你想一想在最优策略里面最后一步可能是怎么发生的然后倒推它和上一步之间的关系。比如爬楼梯最后一步要么是爬1级要么是爬2级所以转移方程就分成两支相加。这一步想通了把方程写出来题目就完成了一大半。第三步确定初始化条件。初始化往往和状态定义里的“空”或者“边界”有关。比如空数组、空字符串、容量为0、走到网格的第一行第一列这些特殊情况的值是什么必须先定下来。5.2 第四步到第五步确认遍历顺序再谈空间优化第四步确定遍历顺序。你要搞清楚计算dp[i]的时候它依赖的dp[i-1]或dp[i-2]是否已经算好了。如果依赖的是上一轮的值你可能需要逆序遍历如果依赖的是本轮的已算值则可以正序遍历。这也就是01背包和完全背包遍历顺序不同的根本原因。第五步空间优化。DP很多情况下可以压缩空间。比如二维dp[i][j]如果只依赖上一行dp[i-1][...]的数据就可以把二维数组压成一行一维数组然后从后往前更新如果依赖的是左上角的数据那还需要用一个单独的变量记住被覆盖的旧值。空间优化不是必须的但面试时主动提出来会显得你理解更深。5.3 空间优化从二维压到一维的通用手法这里把空间优化单独拎出来讲因为它是一个高频考点而且很多初学者会在优化后完全看不懂代码。以01背包为例原始的二维表dp[i][j]只依赖上一行dp[i-1][j]和dp[i-1][j - weight[i]]。换句话说我们只需要保留前一行就能计算出当前行。既然如此为什么不用一行数组反复覆盖呢关键在于必须从后往前更新。因为如果从左往右更新dp[j - weight[i]]可能已经在当前物品上被更新过了这样就会把一个物品用多次。倒序更新dp[j - weight[i]]还是上一轮的值正好符合01背包的语义。再比如LCS的二维表虽然dp[i][j]只依赖左上角、上方、左方三个位置的值但压缩成一维时左上方那个值会被覆盖掉所以你需要用一个prev变量单独记录。这是很多人在空间优化时最容易犯错的地方建议实际写一写对比一下。6. 常见问题与调试技巧刷动态规划踩过的坑6.1 边界条件与数组越界的排查动态规划题目的代码量不大但出错的概率特别高一个常见的原因就是边界条件。我见过最多的问题是数组下标从 0 开始但状态定义用的是“前 i 个”导致 array[i-1] 和 dp[i] 差一位结果一写就错位。建议在做题时先在纸上写清楚“dp[i]中的 i 到底表示前 i 个数还是以下标 i 结尾的数”这两种定义方式对应代码里完全不同的索引写法。另一个问题是数组越界。比如01背包的容量循环里如果weight[i]比背包容量还大那么dp[j - weight[i]]就会越界。解决办法是循环条件写成j weight[i]或者先判断j weight[i]再更新。虽然是小细节但本地编译不报越界面试写代码时却容易被面试官一眼指出来。6.2 状态转移方程写错时的自检方法如果你发现答案不对但代码又看不出明显毛病不要干瞪眼按这个顺序排查。先打印中间结果。把dp数组的每一轮值都输出出来对照手算、脑算的结果很快就能定位到是转移方程写错还是初始化错了。再用小样例验证。用规模很小的输入比如 n3、V5手工把二维表填一遍和代码运行结果对比哪个格子不对改哪个。这个方法笨但非常有效能解决百分之九十以上的DP调试问题。最后检查“最后一个维度”。比如你定义dp[i][j]表示前 i 个物品和前 j 天的情况但转移的时候是否把 i 和 j 的顺序搞混了这种错位经常发生在代码缩写的变量名里一旦看错真的很难发现。6.3 遇到DP题没思路时的破局顺序最后分享一个我刷题时常用的“破局顺序”遇到陌生的动态规划题按这个顺序往下走基本都能找到切入点。第一先看数据范围。如果 n 很小比如 n 20可以考虑状态压缩如果 n 在 10^5 级别大概率是 O(n log n) 的DP优化如果 n 在 10^3 级别那 O(n^2) 的DP大概率可以接受。数据范围会强烈暗示你该用什么量级的解法。第二尝试用暴力搜索的递归思路去解然后观察递归参数里有几个变量。递归函数里的参数基本就是把dp数组的几个维度。比如递归函数是dfs(i, j)那dp[i][j]就八九不离十。第三如果递归思路也能走通再把递归改成递推把递归出口转成初始化条件递归调用转成状态转移方程这样即使你一开始想不到标准DP解也能从暴力搜索演化出正确解法。面试中这个方法特别实用。动态规划的学习不是一蹴而就的我自己也是从一看到DP题就头疼到后来慢慢有能力把每个状态、每个方程讲清楚。这个过程最关键的就是多总结多归类把每道题的“状态定义”和“状态转移”拆出来反复琢磨。等你刷到一定量你会发现动态规划其实就那么几个套路一维线性、二维表格、背包、区间、树形。今天这篇把前三种讲透了后面的内容我们再慢慢深入。
