动态规划算法精讲：从核心思想到LeetCode实战通关指南

1. 项目概述为什么动态规划是算法面试的“定海神针”如果你正在准备技术面试尤其是那些以算法考察闻名的公司那么“动态规划”这四个字大概率已经成了你刷题路上绕不开的一座大山。它不像排序、查找那样直观也不像二叉树遍历那样有固定的套路模板。动态规划Dynamic Programming简称DP更像是一种思想一种将复杂问题分解成重叠子问题并通过存储子问题的解来避免重复计算的优雅策略。我见过太多朋友一看到题目标签里带“DP”就头皮发麻本能地想跳过。但现实是从经典的“爬楼梯”、“斐波那契数列”到面试高频的“最长公共子序列”、“零钱兑换”再到竞赛级的“编辑距离”、“股票买卖系列”动态规划的身影无处不在。可以说掌握它就相当于握住了解决一大类最优化问题的钥匙也是在算法面试中建立自信、拉开差距的关键。我最初学习动态规划时也经历过看概念似懂非懂看题解恍然大悟自己动手却无从下手的阶段。后来经过大量练习和总结我才发现动态规划并非玄学它有一套可以被清晰识别和应用的“解题框架”。这个项目就是把我这些年从LeetCode上百道DP题目中沉淀下来的经验进行一次系统性的“浅析”。所谓“浅析”不是讲得浅而是试图剥开它看似复杂的外壳用最直白的方式讲清楚它的核心思想、识别方法、解题模板并附上精心筛选的LeetCode题目索引帮助你由浅入深地构建自己的DP知识体系。无论你是刚开始刷题的新手还是卡在某个DP专题难以突破的进阶者希望这份融合了原理、模板、真题和避坑经验的总结能成为你手边一份实用的“爬坡指南”。2. 动态规划核心思想与解题框架拆解2.1 从“傻递归”到“记忆化搜索”理解重叠子问题动态规划的核心思想第一步是理解什么是“重叠子问题”。我们用一个最经典的例子——斐波那契数列LeetCode 509来说明。它的定义是F(0)0, F(1)1, F(n)F(n-1)F(n-2) (n2)。如果直接用递归实现代码非常简洁def fib(n): if n 1: return n return fib(n-1) fib(n-2)但这段代码的效率是灾难性的。以计算fib(5)为例它的递归树是这样的计算fib(5)需要先算fib(4)和fib(3)。计算fib(4)需要fib(3)和fib(2)。计算fib(3)需要fib(2)和fib(1)。你会发现fib(3)被计算了两次fib(2)被计算了三次。随着n增大这种重复计算呈指数级增长。这些被反复计算的fib(3)、fib(2)就是“重叠子问题”。动态规划的第一招就是解决这个重复计算问题。最直观的改进是“记忆化搜索”Memoization也叫“自顶向下”的DP。我们用一个数组或字典把已经计算过的子问题的结果存起来。def fib_memo(n, memo{}): if n 1: return n if n not in memo: # 如果没算过才进行计算 memo[n] fib_memo(n-1, memo) fib_memo(n-2, memo) return memo[n] # 算过就直接返回结果这样每个fib(i)都只会被计算一次时间复杂度从恐怖的O(2^n)降到了O(n)。这里的memo字典就是DP中的“状态存储”它是动态规划区别于普通递归的关键。这个例子虽然简单但它揭示了DP最本质的动机通过空间换时间避免对重叠子问题的重复计算。2.2 “自底向上”的递推构建DP表记忆化搜索是理解DP的绝佳起点但在实际面试和竞赛中更常见的写法是“自底向上”的递推也就是显式地构建一张DP表。对于斐波那契数列我们可以这样做定义DP数组dp[i]表示第i个斐波那契数的值。确定初始状态Base Casedp[0] 0,dp[1] 1。这是递推的起点没有它们递推公式无从谈起。确定状态转移方程这就是问题的核心逻辑描述大问题如何由小问题推导而来。对于斐波那契就是dp[i] dp[i-1] dp[i-2] (i 2)。确定遍历顺序由于计算dp[i]需要dp[i-1]和dp[i-2]所以我们需要从i2开始从小到大正向遍历。返回最终结果dp[n]就是我们要求的答案。写成代码就是def fib_dp(n): if n 1: return n dp [0] * (n 1) # 创建DP表 dp[0], dp[1] 0, 1 # 初始化 for i in range(2, n 1): dp[i] dp[i-1] dp[i-2] # 状态转移 return dp[n]注意对于斐波那契数列我们还可以进一步优化空间复杂度。因为dp[i]只依赖于前两个状态所以我们可以只用两个变量滚动更新将空间复杂度从O(n)降到O(1)。但这属于优化技巧在初学阶段理解完整的DP表构建过程更为重要。2.3 动态规划解题的通用四步法通过上面的例子我们可以提炼出解决一个动态规划问题的通用思考框架我习惯称之为“四步法”第一步定义DP数组以及下标的含义状态定义这是最重要的一步直接决定了你能否想出正确的状态转移方程。你需要明确dp[i]或者dp[i][j]到底代表什么。常见的定义有dp[i]以第i个元素结尾的某种最优解如最长递增子序列。dp[i][j]在第一个序列的前i个元素和第二个序列的前j个元素范围内某种最优解如最长公共子序列。dp[i][j]考虑前i个物品在容量为j的背包下能获得的最大价值背包问题。第二步确定状态转移方程递推公式这是动态规划的核心也是最难的一步。你需要用数学公式或逻辑语言清晰地表达出dp[i]是如何由前面的状态如dp[i-1],dp[i-2]或dp[i-1][j],dp[i][j-1]等推导出来的。这需要你对问题有深刻的理解并能够识别出最优子结构。第三步DP数组如何初始化初始状态是递推的基石。你需要根据DP数组的定义给那些无法或不需要通过递推公式计算出来的“起点”状态赋值。例如在斐波那契中dp[0]和dp[1]就是初始状态。初始化错误会导致整个递推结果错误。第四步确定遍历顺序遍历顺序需要保证在计算当前状态时它所依赖的那些子问题状态已经被计算过了。对于一维DP顺序通常比较直观正序或倒序。对于二维DP就需要仔细思考是先遍历行还是先遍历列。在背包问题中遍历顺序更是直接关系到是使用“完全背包”还是“01背包”的解法。第五步验证举例推导DP数组这是检验你前面四步是否正确的最有效方法。不要偷懒动手在纸上画一个小规模的例子比如n5手动推导出整个DP数组的值。这个过程能帮你清晰地验证状态定义、转移方程、初始化和遍历顺序是否全部自洽。很多思路上的漏洞在这一步都会暴露无遗。3. 经典问题深度剖析与LeetCode实战掌握了框架我们把它应用到几类经典的动态规划问题上并关联到具体的LeetCode题目。我会重点讲清状态定义的思路和转移方程的推导。3.1 路径规划问题从“不同路径”到“最小路径和”这类问题通常在一个网格中进行要求从左上角到右下角寻找路径数量或最优路径。LeetCode 62. 不同路径一个机器人位于一个m x n网格的左上角每次只能向下或者向右移动一步。问到达右下角有多少条不同的路径状态定义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]。初始化网格的第一行dp[0][j]和第一列dp[i][0]上的点机器人只有一种走法一直向右或一直向下所以它们都应初始化为1。遍历顺序由于计算(i, j)需要(i-1, j)和(i, j-1)所以我们可以按行从左到右、从上到下遍历。def uniquePaths(m: int, n: int) - int: dp [[1] * n for _ in range(m)] # 初始化第一行第一列都是1 for i in range(1, m): # 从(1,1)开始递推 for j in range(1, n): dp[i][j] dp[i-1][j] dp[i][j-1] return dp[m-1][n-1]LeetCode 64. 最小路径和现在网格中每个格子都有一个非负整数要求找出一条从左上角到右下角的路径使得路径上的数字总和为最小。状态定义dp[i][j]表示从起点(0, 0)走到格子(i, j)的最小路径和。状态转移走到(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初始化第一行和第一列是常见的操作。你可以选择先单独初始化这两条边再计算内部这样逻辑更清晰。也可以像上面“不同路径”的代码一样先全部初始化为一个值再在循环中覆盖代码更简洁但需要确保初始值不会影响递推逻辑例如在求最小值时就不能初始化为0而应该是一个很大的数或者单独处理。3.2 子序列与子数组问题“最长”家族的挑战这是动态规划面试题的绝对主力核心在于如何定义“以某个位置结尾”的状态。LeetCode 300. 最长递增子序列 (LIS)给你一个整数数组nums找到其中最长严格递增子序列的长度。子序列不要求连续。状态定义dp[i]表示以nums[i]这个数结尾的最长递增子序列的长度。为什么这么定义因为这样定义我们才能建立起状态之间的联系。我们关心的是“以某个数结尾”的序列这样在考虑nums[i]时我们可以去扫描它前面所有的数nums[j] (j i)。状态转移对于每一个i遍历它之前的所有位置j。如果nums[i] nums[j]说明nums[i]可以接在nums[j]结尾的子序列后面形成一个更长的递增子序列。所以dp[i] max(dp[i], dp[j] 1)对所有j i且nums[j] nums[i]成立。初始化每个位置本身至少可以构成一个长度为1的子序列所以dp数组全部初始化为1。结果最终结果不是dp[-1]而是dp数组中的最大值因为最长子序列不一定以最后一个元素结尾。def lengthOfLIS(nums): if not nums: return 0 n len(nums) dp [1] * n # 初始化每个元素自身就是一个长度为1的子序列 for i in range(n): for j in range(i): if nums[i] nums[j]: dp[i] max(dp[i], dp[j] 1) return max(dp) # 注意返回最大值时间复杂度是O(n²)。存在一种利用“耐心排序”思想将时间复杂度优化到O(n log n)的贪心二分查找方法但动态规划解法是理解问题的基础。LeetCode 53. 最大子数组和给你一个整数数组nums请你找出一个具有最大和的连续子数组返回其最大和。状态定义dp[i]表示以nums[i]结尾的连续子数组的最大和。状态转移对于nums[i]有两种选择要么单独成为一个子数组从头开始要么接在以nums[i-1]结尾的子数组后面。为了和最大我们选择更大的那个dp[i] max(nums[i], dp[i-1] nums[i])。初始化dp[0] nums[0]。结果同样需要遍历dp数组取最大值。这个问题的状态转移方程非常经典它体现了“当前状态只与前一个状态相关”的特点因此可以像斐波那契数列一样进行空间优化只用一个变量pre来代替整个dp数组。def maxSubArray(nums): n len(nums) max_sum curr_sum nums[0] for i in range(1, n): # curr_sum 相当于 dp[i-1]我们更新它作为 dp[i] curr_sum max(nums[i], curr_sum nums[i]) max_sum max(max_sum, curr_sum) return max_sum3.3 背包问题组合与选择的艺术背包问题是动态规划的另一个核心模型主要解决“选择”与“限制”下的最优解问题。LeetCode 416. 分割等和子集 (01背包应用)给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。问题转化如果能分成两个和相等的子集那么每个子集的和一定是总和的一半记为target。问题就变成了能否从数组中选出一部分数使得它们的和等于target。这就是一个经典的01背包问题——每个数字只能选或不选背包容量是target物品重量和价值都是数字本身的值。状态定义dp[j]表示是否存在一种选择方案使得选取的数字之和恰好等于j。状态转移对于当前数字nums[i]如果我们不选它那么dp[j]的结果保持不变即看之前能否凑出j。如果我们选它那么要能凑出j就需要在没选这个数之前能凑出j - nums[i]。所以dp[j] dp[j] or dp[j - nums[i]](当j nums[i]时)。初始化dp[0] True表示和为0总是可以凑出的什么都不选。其他位置初始化为False。遍历顺序这是一个01背包问题。外层循环遍历物品数组中的数字内层循环倒序遍历背包容量从target到nums[i]。内层倒序是为了保证每个物品最多被使用一次。如果正序遍历一个物品可能会被重复使用这就变成了“完全背包”。def canPartition(nums): total sum(nums) if total % 2 ! 0: # 总和为奇数不可能平分 return False target total // 2 dp [False] * (target 1) dp[0] True # 初始化 for num in nums: for j in range(target, num - 1, -1): # 内层倒序遍历 if dp[j - num]: dp[j] True return dp[target]LeetCode 322. 零钱兑换 (完全背包应用)给你一个整数数组coins表示不同面额的硬币另给一个整数amount表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回 -1。每种硬币的数量无限。问题转化这是一个完全背包问题。背包容量是amount物品是硬币重量是硬币面额价值是硬币个数我们求的是最小个数所以价值是1但目标是“最小化总价值”。状态定义dp[j]表示凑出总金额j所需的最少硬币个数。状态转移对于每个金额j我们遍历所有硬币coin。如果j coin那么我们可以选择用这枚硬币则凑出金额j的最少硬币数可能是dp[j - coin] 1。我们取所有可能中的最小值dp[j] min(dp[j], dp[j - coin] 1)。初始化dp[0] 0凑出金额0需要0个硬币。其他位置初始化为一个很大的数如amount 1或float(inf)表示暂时无法凑出。遍历顺序这是一个完全背包求最小数问题。外层循环遍历背包容量j从0到amount内层循环遍历物品coin。内外层循环的顺序可以互换且内层循环是正序遍历因为物品无限使用。def coinChange(coins, amount): dp [float(inf)] * (amount 1) dp[0] 0 for j in range(1, amount 1): # 遍历背包容量 for coin in coins: # 遍历物品 if j coin: dp[j] min(dp[j], dp[j - coin] 1) return dp[amount] if dp[amount] ! float(inf) else -1注意事项背包问题的遍历顺序是重中之重也是新手最容易出错的地方。简单记01背包物品在外层容量在内层且倒序完全背包求组合数如518.零钱兑换II时物品在外层容量在内层正序求最小数如本题时容量和物品的循环顺序可以互换内层正序。如果不理解就画一个二维的DP表模拟一下不同遍历顺序下状态是如何被覆盖的这是理解的根本。4. LeetCode动态规划题目分类索引与进阶路线有了对经典问题的理解我们可以按图索骥进行系统性的刷题练习。我根据难度和类型整理了一份精选的LeetCode DP题目索引并附上简要的核心考察点你可以把它当作一个爬坡路线图。4.1 入门与基础建立信心这些题目是理解DP思想的绝佳起点状态定义和转移相对直观。70. 爬楼梯斐波那契数列变种dp[i] dp[i-1] dp[i-2]。118. 杨辉三角理解二维DP的填充过程。121. 买卖股票的最佳时机简单的一次买卖可以不用DP但用DP思路记录历史最低价能衔接后续复杂股票问题。198. 打家劫舍经典的一维序列选择问题dp[i] max(dp[i-1], dp[i-2] nums[i])。746. 使用最小花费爬楼梯爬楼梯的代价版dp[i] min(dp[i-1], dp[i-2]) cost[i]。4.2 二维DP与路径问题巩固思维在网格中思考问题培养二维状态定义能力。62. 不同路径(已详解)63. 不同路径 II增加了障碍物在转移时需判断。64. 最小路径和(已详解)120. 三角形最小路径和自底向上递推更简洁dp[j] min(dp[j], dp[j1]) triangle[i][j]。4.3 子序列与子数组问题面试高频这是DP的重灾区需要反复练习状态定义“以i结尾”的套路。53. 最大子数组和(已详解)300. 最长递增子序列(已详解)1143. 最长公共子序列二维DP经典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])。718. 最长重复子数组要求连续定义dp[i][j]为以nums1[i-1]和nums2[j-1]结尾的最长公共子数组长度相等时dp[i][j]dp[i-1][j-1]1。392. 判断子序列双指针简单但用DPLCS思路也可解能衔接更复杂问题。115. 不同的子序列困难题计数类DPdp[i][j]表示s[0:i]中t[0:j]出现的个数。4.4 背包问题专题掌握模型彻底理解01背包和完全背包的几种变体。416. 分割等和子集(01背包判断可行性)494. 目标和(01背包计数问题需转化思路)474. 一和零(二维费用的01背包)322. 零钱兑换(完全背包求最小数)518. 零钱兑换 II(完全背包求组合数)279. 完全平方数(完全背包求最小数物品是平方数)4.5 字符串编辑与匹配问题难度提升这类问题通常涉及两个字符串的比对状态定义和转移需要更细致的考量。72. 编辑距离经典难题dp[i][j]表示将word1[0:i]转换为word2[0:j]的最小操作数分增、删、改三种情况讨论。10. 正则表达式匹配困难题状态转移需要考虑*和.的特殊匹配规则。44. 通配符匹配与正则匹配类似但规则不同。4.6 状态机与复杂DP思维拓展一些题目需要定义包含多个状态的状态或者结合其他算法思想。121-123, 188. 买卖股票的最佳时机系列这个系列是学习状态机DP的完美教材。通常定义dp[i][k][0/1]表示第i天最多交易k次手上持有(1)或不持有(0)股票的最大利润。152. 乘积最大子数组由于负负得正需要同时维护以i结尾的最大乘积max_dp[i]和最小乘积min_dp[i]。337. 打家劫舍 III树形DP结合二叉树后序遍历每个节点返回一个二维状态[rob, not_rob]。139. 单词拆分DP序列划分问题dp[i]表示s[0:i]能否被拆分内层循环枚举分割点j。4.7 区间DP与其他竞赛向难度较高常用于解决回文串、石子合并等区间最优问题。5. 最长回文子串中心扩散法更优但DP解法dp[i][j]表示s[i:j]是否回文也是经典思路。516. 最长回文子序列区间DPdp[i][j]表示s[i:j]中最长回文子序列长度。312. 戳气球经典区间DP难题定义dp[i][j]为戳破开区间(i,j)内所有气球能获得的最大硬币。5. 动态规划刷题常见“坑点”与调试技巧即使理解了原理和框架实际做题时还是会踩很多坑。下面是我总结的一些高频“坑点”和应对策略。5.1 初始化与边界条件处理这是导致答案错误的最常见原因之一。数组越界在访问dp[i-1],dp[i-2]或者dp[i-1][j]时一定要确保i-1,i-2,j-1是有效的索引。通常需要在循环开始前对i0,1或第一行、第一列进行单独的初始化。初始值含义dp[0]或dp[0][0]到底应该是什么在求最大值/最小值问题时初始值有时需要设为负无穷或正无穷。例如在“最大子数组和”的优化解法中curr_sum初始为nums[0]而不是0因为数组可能全为负数。“无解”状态的表示在像“零钱兑换”这种可能无解的问题中DP数组的初始值除了dp[0]应该设为一个不可能达到的“坏值”如float(inf)或amount1最后通过判断这个值是否被更新来确定是否有解。调试技巧在写出代码后立刻用最小的、非平凡的例子测试边界。比如n0, n1, 空数组单个元素数组等。很多边界错误在这里就能发现。5.2 遍历顺序的陷阱遍历顺序必须保证在计算当前状态时它所依赖的子问题状态已经被计算并存储。01背包内层必须倒序这是重中之重。如果求组合数如dp[j] dp[j-nums[i]]正序遍历会导致物品被重复使用。你可以这样记忆倒序是为了“保证每个物品只被考虑一次”因为dp[j]更新时依赖的是上一轮i-1的dp[j-nums[i]]而不是本轮已经更新过的。二维DP的遍历顺序对于dp[i][j]如果你按行遍历那么计算dp[i][j]时dp[i-1][j]上一行肯定已算好dp[i][j-1]本行左侧也因为从左到右遍历而已算好。顺序是合理的。如果状态转移依赖dp[i1][j-1]这种就需要仔细设计遍历顺序甚至从后往前遍历。涉及多个维度的依赖在股票问题系列中状态可能同时依赖i-1前一天和k-1少一次交易这就需要确定是先遍历i还是先遍历k。通常时间i作为最外层循环是符合逻辑的。调试技巧当对遍历顺序不确定时画DP表在纸上画一个3x3或4x4的表格手动模拟你的代码按照某种顺序填充表格的过程看每个格子填充时它依赖的格子是否已经填好。这是最直观、最有效的验证方法。5.3 空间优化时的状态覆盖问题当我们用滚动数组或单个变量来优化空间时要特别注意状态的覆盖顺序。一维DP优化如斐波那契数列用a, b, c三个变量滚动。关键是更新顺序c a b; a b; b c;。顺序错了值就乱了。01背包优化到一维内层循环倒序本身就是空间优化后的写法它天然避免了状态覆盖问题。如果你尝试写二维的再优化到一维就能理解为什么必须倒序。二维DP优化到一维滚动数组例如“不同路径”我们可以只用一行dp[j]来表示。计算dp[j]时它左边的dp[j-1]是当前行更新过的相当于dp[i][j-1]它上面的dp[j]是上一行旧的相当于dp[i-1][j]。所以状态转移dp[j] dp[j] dp[j-1]是成立的。这里的dp[j]在赋值前代表上一行的值赋值后代表当前行的值。实操心得在面试或笔试时不建议一上来就写空间优化后的代码。除非你对问题极其熟练。更稳妥的做法是先写出清晰、正确的二维或标准一维DP解法确保逻辑正确。然后如果时间允许或者面试官要求再解释如何进行空间优化。这样既能展示你的思维过程又能避免在优化时引入难以察觉的bug。5.4 复杂问题如何寻找状态定义对于没见过的新题如何定义DP状态我通常尝试以下思路从问题本身出发题目求什么状态就可能表示什么。求最长/最大/最小dp[i]就可能是以i结尾的最优值。求是否可行dp[i]就可能是布尔值。尝试增加维度如果一维状态无法涵盖所有信息比如股票问题中的交易次数、持有状态就增加维度。dp[i][k]或dp[i][0/1]。类比经典模型看看问题是否像背包选择/容量、序列编辑两个序列比对、区间分割等经典模型。如果能归类就可以套用或修改经典的状态定义。从小规模枚举在纸上手动枚举n1,2,3的情况观察答案是如何从小规模问题推导到大规模问题的。这个推导关系往往就是状态转移方程。最后也是最重要的一点动态规划的能力无法一蹴而就。它需要大量的练习和总结。我的建议是按照上面提供的题目索引从一个专题开始集中刷5-10道题。每道题不要只满足于AC要问自己状态为什么这么定义转移方程怎么来的遍历顺序为何如此能不能优化空间然后合上答案自己从头到尾再写一遍。坚持这个过程你会发现自己对DP的感觉会越来越清晰那道曾经高不可攀的“大山”最终会成为你算法工具箱里最得心应手的利器之一。