1. 从“爬楼梯”到“最优解”动态规划的直觉建立如果你刷过LeetCode或者准备过技术面试那么“动态规划”这四个字大概率是你绕不开的一座大山。它不像排序、链表那样直观也不像二叉树那样有固定的遍历模式。很多人第一次接触动态规划Dynamic Programming简称DP时都会觉得它既神秘又复杂——状态、转移方程、最优子结构、重叠子问题……一堆术语砸下来直接把人搞懵。但我想说动态规划的核心思想其实非常朴素甚至可以说是一种“聪明的穷举”。它源于我们解决复杂问题时一种本能的思考方式记住已经解决过的子问题的答案避免重复计算。我们从一个最经典的入门题开始建立这种直觉。LeetCode 70. 爬楼梯假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶最直接的暴力想法是递归要爬到第n阶我可以从第n-1阶爬1步上来也可以从第n-2阶爬2步上来。所以f(n) f(n-1) f(n-2)。这就是状态转移方程的雏形。如果我们直接写递归代码会发现计算f(5)时需要f(4)和f(3)计算f(4)又需要f(3)和f(2)……f(3)被重复计算了多次。当n很大时这种重复是指数级增长的效率极低。动态规划在这里做了什么它说既然f(3)会被用到很多次那我们为什么不第一次算出来之后就把它存起来呢于是我们开一个数组dpdp[i]表示爬到第i阶楼梯的方法数。我们知道dp[1] 1爬1阶dp[2] 2一次爬2阶或分两次各爬1阶。那么对于i 3dp[i] dp[i-1] dp[i-2]。我们只需要从i3开始一路算到in每个dp[i]只计算一次最后返回dp[n]即可。这个过程揭示了动态规划的两个核心性质最优子结构问题的最优解可以由其子问题的最优解构造出来。爬到第n阶的最优解方法总数由爬到第n-1阶和第n-2阶的最优解方法总数推导而来。重叠子问题在递归求解过程中相同的子问题被反复计算。动态规划通过列表记忆化避免了这种重复。所以动态规划不是什么魔法它就是一种用空间换时间的策略通过系统地记录并复用子问题的解来高效解决具有重叠子问题的优化问题。很多看似复杂的题目其内核就是这个简单的思想。接下来我们会拆解动态规划的解题框架并用不同类型的LeetCode经典题目来填充这个框架让你不仅知道怎么做更明白为什么这么做。2. 动态规划解题的标准化四步框架理解了核心思想后我们需要一个可重复、可实践的解题步骤。经过大量题目训练我总结了一套四步法几乎适用于所有动态规划问题。这套方法能帮你从一团乱麻中理清头绪。2.1 第一步定义状态数组dp数组及其含义这是最关键的一步直接决定了问题能否被正确解决。状态的定义需要准确描述当前问题的某个“局面”。通常dp[i]或者dp[i][j]代表的是在某种限制条件下考虑到前i个元素或处于i位置、拥有i容量等时我们想要的那个最优值最大、最小、方法数等。关键思考题目问什么状态就定义什么。但需要找到那个可以递推的“维度”。问最大利润dp[i]可能表示第i天结束时的最大利润。问能否分割dp[i]可能表示字符串前i个字符能否被成功分割。问最长子序列dp[i]可能表示以第i个元素结尾的某种子序列的最大长度。涉及两个维度如字符串比较、背包问题dp[i][j]就非常常见表示考虑第一个序列的前i个元素和第二个序列的前j个元素时的状态。经验之谈很多初学者喜欢一上来就想转移方程这很容易卡住。先静下心来问自己“我需要用什么信息来描述当前走到哪一步了我想要的结果如何用这个信息表达出来” 把状态定义写在注释里是很好的习惯。2.2 第二步推导状态转移方程这是动态规划的灵魂也是最考验逻辑思维能力的一步。我们需要找出dp[i]或dp[i][j]与之前的状态通常是dp[i-1]dp[i-2]dp[i-1][j-1]等之间的关系。可以问自己这样一个问题“要达到当前状态有哪几种可能的选择或上一个状态是什么每种选择对应的结果是什么”回到爬楼梯问题要达到第i阶要么从i-1阶走1步要么从i-2阶走2步。所以dp[i] dp[i-1] dp[i-2]。这就是转移方程。再比如 LeetCode 122. 买卖股票的最佳时机 II无限交易次数定义dp[i][0]表示第i天交易结束后持有股票的最大利润dp[i][1]表示第i天交易结束后不持有股票的最大利润。对于dp[i][0]我今天持有股票要么是昨天就持有今天没动 (dp[i-1][0])要么是昨天不持有今天买入 (dp[i-1][1] - prices[i])。两者取最大值。对于dp[i][1]我今天不持有股票要么是昨天就不持有 (dp[i-1][1])要么是昨天持有今天卖出 (dp[i-1][0] prices[i])。两者取最大值。 方程就出来了dp[i][0] max(dp[i-1][0], dp[i-1][1] - prices[i])dp[i][1] max(dp[i-1][1], dp[i-1][0] prices[i])注意推导时一定要结合状态定义。dp[i]是“以 i 结尾”还是“考虑前 i 个”对应的转移方程可能天差地别。2.3 第三步确定初始状态Base Case递推需要有起点否则就会像没有第一块骨牌的多米诺。初始状态是那些不能再被分解的、最基础子问题的解。通常我们需要手动设置dp[0]、dp[1]或者dp[0][j]、dp[i][0]的值。爬楼梯dp[1] 1,dp[2] 2。注意这里n从1开始为了代码健壮性需要处理n0或n1的边界。背包问题dp[0][j]表示容量为 j 的包装0件物品价值自然是0。dp[i][0]表示容量为0的包能装的价值也是0。字符串类问题空字符串往往对应dp[0]其值需要根据题意确定比如空串能否匹配等。踩坑点初始状态设置错误会导致整个递推结果全错。务必结合题目含义仔细检查。一个技巧是在纸上画一个小的、具体的例子手动推导前几步来验证你的状态定义、转移方程和初始状态是否自洽。2.4 第四步确定遍历顺序与计算最终结果这一步关乎代码如何正确无误地执行。遍历顺序要保证在计算dp[i]时它所依赖的所有子状态如dp[i-1],dp[i-2]都已经被计算并存储好了。对于一维dp通常是从前向后如爬楼梯或从后向前如完全背包的某些变体遍历。对于二维dp要搞清楚i和j的依赖关系决定是逐行遍历还是逐列遍历或者斜向遍历。最终结果状态定义是什么最终答案往往就是哪个状态。可能是dp[n]可能是dp[n-1][m-1]也可能是整个dp数组中的最大值如最长递增子序列。将这四步套用到任何DP问题上你的思路会清晰很多。下面我们就用这个框架去攻克几类经典的动态规划问题。3. 线性动态规划序列上的经典问题这类问题的状态通常只与序列的前一个或前几个位置相关是理解DP的基础。3.1 最长递增子序列LISLeetCode 300这是面试中的常客。题目要求找到数组中最长的、严格递增的子序列的长度。状态定义dp[i]表示以nums[i]这个数结尾的最长递增子序列的长度。注意这里必须是“以 i 结尾”因为这样我们才能通过连接nums[i]来形成新的子序列。如果定义为“前 i 个元素中的最长子序列长度”则无法方便地判断能否连接nums[i]。转移方程对于每个i我们需要遍历j从0到i-1。如果nums[i] nums[j]说明nums[i]可以接在nums[j]结尾的子序列后面形成一个更长的递增子序列。因此dp[i] max(dp[i], dp[j] 1)对所有满足nums[i] nums[j]的j成立。如果没有任何j满足条件那么dp[i] 1子序列只包含自身。初始状态每个位置至少可以以自己为子序列所以初始时dp[i] 1。遍历与结果外层i从0到n-1遍历内层j从0到i-1遍历。最终结果不是dp[n-1]而是整个dp数组中的最大值因为最长子序列不一定以最后一个元素结尾。复杂度与优化上述解法时间复杂度 O(n²)。存在一种利用“耐心排序”思想、结合二分查找的 O(n log n) 优化解法维护一个“有序的尾部最小元素数组”这里不展开但知道有更优解对面试很重要。3.2 最大子数组和LeetCode 53给你一个整数数组nums请你找出一个具有最大和的连续子数组返回其最大和。状态定义dp[i]表示以nums[i]结尾的连续子数组的最大和。同样定义成“以 i 结尾”是为了保证子数组的连续性。转移方程对于nums[i]只有两种选择要么单独成为一个子数组 (nums[i])要么接在以nums[i-1]结尾的子数组后面 (dp[i-1] nums[i])。我们要取和最大的那种所以dp[i] max(nums[i], dp[i-1] nums[i])。初始状态dp[0] nums[0]。遍历与结果从i1开始遍历。最终结果是dp数组中的最大值。空间优化由于dp[i]只依赖于dp[i-1]我们可以只用一个变量pre来记录前一个状态将空间复杂度从 O(n) 降到 O(1)。这是动态规划常见的优化手段。def maxSubArray(nums): n len(nums) max_sum curr_sum nums[0] for i in range(1, n): # 这里的 curr_sum 就相当于 dp[i-1] # 我们计算新的 curr_sum (即 dp[i]) curr_sum max(nums[i], curr_sum nums[i]) # 随时更新全局最大值 max_sum max(max_sum, curr_sum) return max_sum3.3 打家劫舍系列LeetCode 198 213这个系列是理解状态定义的绝佳例子。LeetCode 198. 打家劫舍一排房屋不能偷相邻的两家求最大收益。状态定义dp[i]表示考虑偷前 i 间房屋不一定偷第 i 间能获得的最大金额。这是一种常见的定义方式。转移方程对于第i间房下标i-1有两种选择偷它那么第i-1间不能偷收益是dp[i-2] nums[i-1]。不偷它那么收益就是dp[i-1]。 取最大值dp[i] max(dp[i-1], dp[i-2] nums[i-1])。初始状态dp[0] 0没有房屋dp[1] nums[0]只有一间房必偷。结果dp[n]。LeetCode 213. 打家劫舍 II房屋围成一圈其他条件相同。核心矛盾首尾相连偷了第一家就不能偷最后一家。解题技巧既然首尾不能同时偷我们可以把环拆成两个线性问题考虑偷第一家不偷最后一家计算范围[0, n-2]的最大收益。考虑不偷第一家可以偷最后一家计算范围[1, n-1]的最大收益。 最终结果是这两个线性问题结果的最大值。这体现了动态规划中“分类讨论”的思想。4. 背包问题从01背包到完全背包背包问题是动态规划的另一个核心范式主要解决“选择”与“限制”下的最优组合问题。4.1 01背包问题每个物品最多选一次问题原型有N件物品和一个容量为V的背包。第i件物品的体积是weight[i]价值是value[i]。求解将哪些物品装入背包可使价值总和最大且不超过背包容量。状态定义最经典的定义是dp[i][j]表示从前 i 件物品中选择放入容量为 j 的背包中可以获取的最大价值。转移方程对于第i件物品实际下标i-1我们面临选择不选那么最大价值就是dp[i-1][j]即前i-1件物品在容量j下的最大价值。选前提是背包容量j weight[i-1]。如果选那么背包需要预留出weight[i-1]的容量给这个物品剩下的j - weight[i-1]容量用来装前i-1件物品。总价值为dp[i-1][j - weight[i-1]] value[i-1]。 两者取最大值dp[i][j] max(dp[i-1][j], dp[i-1][j - weight[i-1]] value[i-1])。初始状态dp[0][j] 00件物品价值为0dp[i][0] 0容量为0价值为0。遍历顺序外层循环遍历物品i从1到N内层循环遍历背包容量j从1到V。注意内层循环可以正序也可以倒序但在空间优化时至关重要。空间优化滚动数组观察转移方程dp[i][j]只依赖于dp[i-1][...]即上一行的数据。因此我们可以将二维数组压缩成一维数组dp[j]。但此时内层循环必须倒序从V到weight[i-1]遍历原因在于如果正序遍历在计算dp[j]时dp[j - weight[i-1]]可能已经被本轮的更新覆盖了即变成了“考虑过当前物品”的状态这就相当于同一件物品被多次选取违背了01背包“每个物品仅一次”的规则。倒序遍历可以保证dp[j - weight[i-1]]使用的是上一轮即未考虑当前物品的状态。# 01背包 一维dp数组写法 def knapsack_01(N, V, weight, value): dp [0] * (V 1) for i in range(N): # 遍历物品 for j in range(V, weight[i] - 1, -1): # 倒序遍历容量 dp[j] max(dp[j], dp[j - weight[i]] value[i]) return dp[V]4.2 完全背包问题每个物品无限次选取与01背包的唯一区别是每种物品有无限件。状态定义同上dp[i][j]。转移方程dp[i][j] max(dp[i-1][j], dp[i][j - weight[i-1]] value[i-1])。注意第二个选项是dp[i][j - weight[i-1]]而不是dp[i-1][...]。这是因为即使考虑了前i件物品我们仍然可以再次选择第i件物品因为它无限多。空间优化与遍历顺序使用一维数组时内层循环需要正序遍历容量。这正是因为完全背包允许重复选取我们需要dp[j - weight[i-1]]是已经考虑过当前物品i的状态。正序遍历恰好能满足这个要求。# 完全背包 一维dp数组写法 def knapsack_complete(N, V, weight, value): dp [0] * (V 1) for i in range(N): # 遍历物品 for j in range(weight[i], V 1): # 正序遍历容量 dp[j] max(dp[j], dp[j - weight[i]] value[i]) return dp[V]LeetCode上的背包问题416. 分割等和子集可以转化为01背包。背包容量为sum/2物品重量和价值都是nums[i]看是否能恰好装满背包。494. 目标和可以转化为01背包。需要一点数学推导找到需要正数的和。322. 零钱兑换完全背包问题。背包容量是amount物品是硬币面额coins价值是1硬币个数求最小价值最少硬币数。注意这里是求最小值初始化和max要改为min。518. 零钱兑换 II完全背包问题但求的是组合数方法数。dp[j]表示凑成金额j的组合数。转移方程为dp[j] dp[j - coin]。重要心得遇到背包类问题先抽象出“容量”和“物品”然后判断是01背包每个物品选一次还是完全背包物品无限最后根据问题是求最大价值、能否装满、最少物品数还是组合数来调整状态定义、初始化和转移方程。5. 区间与双序列动态规划这类问题通常涉及两个序列如字符串的比较或者一个序列上的区间操作状态通常是二维的dp[i][j]。5.1 最长公共子序列LCSLeetCode 1143给定两个字符串text1和text2返回它们的最长公共子序列的长度。状态定义dp[i][j]表示text1的前i个字符[0:i)和text2的前j个字符[0:j)的最长公共子序列长度。通常会让dp数组大小为(m1) x (n1)dp[0][j]和dp[i][0]表示空串。转移方程考虑text1[i-1]和text2[j-1]这两个字符。如果它们相等那么这个字符一定在LCS中。dp[i][j] dp[i-1][j-1] 1。如果它们不相等那么LCS不可能同时包含它们。LCS可能来自text1的前i-1和text2的前j个字符也可能来自text1的前i和text2的前j-1个字符。取最大值dp[i][j] max(dp[i-1][j], dp[i][j-1])。初始状态dp[0][j] 0,dp[i][0] 0。遍历顺序两层循环i从1到mj从1到n。顺序无关紧要因为dp[i][j]依赖于其左、上、左上三个方向的状态。结果dp[m][n]。5.2 编辑距离LeetCode 72给你两个单词word1和word2请你计算出将word1转换成word2所使用的最少操作数插入、删除、替换一个字符。状态定义dp[i][j]表示将word1的前i个字符转换为word2的前j个字符所需的最少操作数。转移方程考虑对word1[i-1]的操作。如果word1[i-1] word2[j-1]不需要操作dp[i][j] dp[i-1][j-1]。如果不等我们有三种选择取最小值删除word1[i-1]操作数 dp[i-1][j] 1插入一个字符到word1相当于匹配word2[j-1]操作数 dp[i][j-1] 1替换word1[i-1]为word2[j-1]操作数 dp[i-1][j-1] 1dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1初始状态dp[i][0] i将i个字符全部删除dp[0][j] j插入j个字符。结果dp[m][n]。踩坑点初始状态很容易想错。牢记dp[i][j]的定义是“转换所需步数”从空串到长度为i的串自然需要i次插入操作。5.3 回文子串与子序列LeetCode 647. 回文子串计算字符串中回文子串的数目。状态定义dp[i][j]表示字符串s的子串[i, j]是否是回文串布尔值。转移方程首先如果s[i] ! s[j]肯定不是回文。 如果s[i] s[j]那么如果j - i 1即长度为1或2肯定是回文。否则取决于内部子串[i1, j-1]是否是回文即dp[i1][j-1]。 所以dp[i][j] (s[i] s[j]) and (j - i 1 or dp[i1][j-1])。遍历顺序这里dp[i][j]依赖于dp[i1][j-1]即左下方的状态。因此不能简单地i从0到nj从0到n。需要保证在计算dp[i][j]时dp[i1][j-1]已经被计算过了。一种常见的遍历方式是外层循环枚举子串长度L从1到n内层循环枚举起点i从而确定终点j i L - 1。结果统计所有dp[i][j] True的个数。LeetCode 516. 最长回文子序列求最长回文子序列的长度子序列不要求连续。状态定义dp[i][j]表示字符串s在区间[i, j]内的最长回文子序列长度。转移方程如果s[i] s[j]那么这两个字符可以贡献到回文子序列中dp[i][j] dp[i1][j-1] 2。如果s[i] ! s[j]那么这两个字符不可能同时出现在最长回文子序列中。分别考虑去掉s[i]或s[j]的情况取最大值dp[i][j] max(dp[i1][j], dp[i][j-1])。初始状态dp[i][i] 1单个字符是回文。遍历顺序类似于回文子串需要从小区间向大区间递推。可以采用长度L从2到n的遍历方式。结果dp[0][n-1]。6. 状态机动态规划处理复杂状态转移有些问题的状态不是简单的“选或不选”而是有多个状态之间相互转换。股票买卖系列是这类问题的典型代表。我们已经见过LeetCode 122无限交易现在看一个更复杂的。LeetCode 309. 最佳买卖股票时机含冷冻期卖出股票后你无法在第二天买入股票即冷冻期为1天。状态定义我们需要更细致地刻画每天结束时的状态。通常定义三种状态dp[i][0]: 第i天结束时持有股票的最大利润。dp[i][1]: 第i天结束时不持有股票且处于冷冻期即今天卖出了股票。dp[i][2]: 第i天结束时不持有股票且不处于冷冻期。转移方程思考每个状态昨天可能是什么状态dp[i][0]今天持有要么昨天就持有 (dp[i-1][0])要么昨天不持有且非冷冻期今天买入 (dp[i-1][2] - prices[i])。不能从冷冻期买入因为冷冻期不能操作。dp[i][1]今天卖出进入冷冻期那昨天必须持有股票然后今天卖出。所以dp[i][1] dp[i-1][0] prices[i]。dp[i][2]今天不持有且非冷冻期说明今天没有任何操作。那么昨天结束时可能是不持有股票的任何状态冷冻期或非冷冻期。所以dp[i][2] max(dp[i-1][1], dp[i-1][2])。初始状态dp[0][0] -prices[0]第一天买入dp[0][1] 0第一天不可能卖出但可初始化为0不影响后续dp[0][2] 0第一天不操作结果最后一天第n-1天结束时持有股票肯定不是最优的因为没卖掉所以结果是max(dp[n-1][1], dp[n-1][2])。这种“状态机”的思考方式能将复杂的约束条件如冷冻期清晰地建模出来是解决此类问题的利器。关键在于定义出所有可能的状态并厘清状态之间如何合法地转换。7. 路径规划与多维动态规划这类问题通常在一个矩阵或网格中寻找最优路径状态与位置(i, j)相关。LeetCode 62. 不同路径63. 不同路径 II机器人从左上角走到右下角只能向右或向下走求路径总数。63题增加了障碍物。状态定义dp[i][j]表示从起点(0,0)走到(i,j)的路径总数。转移方程由于只能向右或向下所以要走到(i,j)上一步只可能是从(i-1,j)下来或者从(i,j-1)过来。所以dp[i][j] dp[i-1][j] dp[i][j-1]。初始状态对于62题无障碍第一行和第一列的所有位置都只有一条路径一直向右或一直向下所以dp[0][j] 1,dp[i][0] 1。障碍物处理63题如果(i,j)是障碍物则dp[i][j] 0。此外初始化第一行和第一列时一旦遇到一个障碍物后面的位置也都不可达路径数为0。遍历顺序两层循环i从0到m-1j从0到n-1。因为dp[i][j]依赖于其上方和左方的状态这个顺序是合理的。结果dp[m-1][n-1]。LeetCode 64. 最小路径和在网格中找一条从左上到右下的路径使得路径上的数字总和最小。状态定义dp[i][j]表示从起点(0,0)走到(i,j)的最小路径和。转移方程dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]。初始状态dp[0][0] grid[0][0]。第一行只能从左来dp[0][j] dp[0][j-1] grid[0][j]。第一列只能从上来dp[i][0] dp[i-1][0] grid[i][0]。结果dp[m-1][n-1]。个人体会网格类DP是相对直观的难点往往在于处理边界条件第一行、第一列和障碍物。在纸上画一个3x3的小网格手动推导一下dp数组能极大地帮助理解初始化和转移过程避免下标越界等低级错误。动态规划的世界远不止于此还有树形DP、状压DP、数位DP等更高级的主题。但掌握以上这些经典模型和四步解题法足以应对绝大多数面试和竞赛中的DP问题。核心永远是定义清晰的状态找到正确的转移处理好边界然后优雅地遍历。剩下的就是通过大量的练习将这种思维模式内化成本能。当你再看到一道新题能下意识地去思考“它的状态是什么怎么转移”的时候你就已经跨过动态规划这道坎了。