动态规划详解：从入门到精通，这四个案例让你彻底掌握DP思想

面试必考、算法进阶的核心一篇文章帮你打通任督二脉在算法学习的过程中动态规划Dynamic Programming简称DP绝对是让很多人头疼的一个难点。很多初学者看到DP问题就发怵其实只要掌握了核心思想你会发现DP问题并没有想象中那么难。今天我将用最通俗易懂的方式结合四个经典案例带你彻底掌握动态规划的精髓。一、什么是动态规划动态规划与分治法类似都是通过将原问题拆分为若干子问题然后递归求解子问题最后再组合子问题的解来得到原问题的解。但两者有一个本质区别分治法解决的子问题通常相互独立比如快速排序、归并排序动态规划解决的子问题具有重叠现象——不同的子问题会包含相同的子子问题举个例子计算斐波那契数列时fib(5)需要计算fib(4)和fib(3)而fib(4)又需要计算fib(3)和fib(2)这里的fib(3)就被重复计算了两次。如果不加干预这些重复的子问题会被多次计算导致效率极低。动态规划的核心思想就是保证每个重复的子问题只计算一次通过将计算过的子问题保存起来后续直接获取结果。动态规划的两种实现方式自上而下的记忆化递归从原问题出发递归求解子问题并用缓存记录已计算的结果自下而上的迭代从最小子问题开始逐步递推到原问题二、案例一爬楼梯问题力扣70题爬有n个台阶的楼梯每次可以爬1或2个台阶问有多少种不同的方法可以爬到楼顶问题分析这是一个非常经典的动态规划入门题。我们思考一下要到达第n个台阶最后一步可能是从第n-1个台阶爬1阶上来的也可能是从第n-2个台阶爬2阶上来的。因此爬到第n阶的方法数就等于爬到第n-1阶的方法数加上爬到第n-2阶的方法数。状态转移方程textf(n) f(n-1) f(n-2)边界条件f(1) 1只有一种方法爬1阶f(2) 2两种方法11 或 2方法一暴力递归不推荐pythondef climb(n): if n 1: return 1 elif n 2: return 2 else: return climb(n-1) climb(n-2)这种方法的缺点很明显存在大量重复计算时间复杂度为O(2^n)当n较大时效率极低。方法二自下而上的迭代推荐pythondef climb(n): pre 1 # 前一个状态对应f(1) cur 1 # 当前状态对应f(2) for _ in range(1, n): pre, cur cur, pre cur return cur这种方法只使用了两个变量空间复杂度O(1)时间复杂度O(n)非常高效。核心思想从基础状态开始逐步推导出目标状态每个状态只计算一次。三、案例二最大连续子数组之和力扣53题找出整数数组中数组之和最大的连续子数组返回其最大和。示例nums [-2,1,-3,4,-1,2,1,-5,4]输出6子数组[4,-1,2,1]问题分析这道题的关键在于如何定义状态。我们定义f(i)表示以第i个元素结尾的最大子数组之和。当遍历到位置i时有两种选择延续之前的子数组将当前元素加入到之前的子数组中此时f(i) f(i-1) nums[i]重新开始新的子数组放弃之前的子数组从当前元素重新开始此时f(i) nums[i]我们选择两者中较大的那个因此得到状态转移方程textf(i) max(f(i-1) nums[i], nums[i])代码实现pythondef max_subarray(nums): result nums[0] # 全局最大值 f 0 # 以当前元素结尾的最大子数组和 for i in nums: # 如果之前的子数组和小于0则中断连续重新开始 if f 0: f 0 # 累加当前元素 f i # 更新全局最大值 if result f: result f return result关键点理解为什么当f0时要重置为0因为如果之前的子数组和是负数加上它只会让当前子数组和变小不如从当前元素重新开始。这就是“负数会拖累整体”的思想。四、案例三0-1背包问题0-1背包问题是动态规划的经典问题给定一组物品每个物品有重量和价值在背包容量有限的情况下如何选择物品使得总价值最大问题描述物品重量价值013122236背包容量W5求能装的最大价值。方法一二维DP1定义状态dp[i][j]表示考虑前i个物品0到i背包容量为j时能够获得的最大价值。2状态转移对于每个物品i有两种选择不选第i个物品此时最大价值就是前i-1个物品在容量j下的最大价值即dp[i-1][j]选第i个物品此时需要腾出weight[i]的空间所以最大价值为value[i] dp[i-1][j-weight[i]]前提是j weight[i]状态转移方程textdp[i][j] max(dp[i-1][j], value[i] dp[i-1][j-weight[i]])3代码实现pythondef knapsack(weights, values, W): n len(weights) # 初始化二维数组 dp [[0] * (W 1) for _ in range(n)] for i in range(n): for j in range(1, W 1): if weights[i] j: # 放得下比较放与不放哪个更好 dp[i][j] max(dp[i-1][j], values[i] dp[i-1][j-weights[i]]) else: # 放不下只能沿用上一行的结果 dp[i][j] dp[i-1][j] return dp[n-1][W]方法二一维DP空间优化观察二维DP的递推过程我们发现每一行只依赖上一行的数据因此可以用一维数组来优化空间。关键点遍历背包容量时必须从后往前避免本轮更新的结果被重复使用因为0-1背包每个物品只能选一次。pythondef knapsack(weights, values, W): n len(weights) dp [0] * (W 1) for i in range(n): # 从后往前遍历确保每个物品只被考虑一次 for j in range(W, weights[i] - 1, -1): dp[j] max(dp[j], values[i] dp[j - weights[i]]) return dp[W]五、案例四完全背包问题完全背包是0-1背包的扩展不同之处在于每个物品可以被选取多次数量无限。问题分析状态定义与0-1背包相同dp[i][j]表示前i个物品中容量为j时的最大价值。但状态转移发生了变化不选第i个物品仍然为dp[i-1][j]选第i个物品因为可以重复选择所以选完之后还可以继续选第i个物品因此是value[i] dp[i][j-weight[i]]注意这里是dp[i]而不是dp[i-1]状态转移方程textdp[i][j] max(dp[i-1][j], value[i] dp[i][j-weight[i]])一维DP优化从前向后遍历完全背包的一维优化与0-1背包正好相反需要从前往后遍历因为可以重复使用当前物品的结果。pythondef knapsack(weights, values, W): n len(weights) dp [0] * (W 1) for i in range(n): # 从前往后遍历允许重复选择当前物品 for j in range(weights[i], W 1): dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[W]0-1背包 vs 完全背包一维优化的对比对比项0-1背包完全背包遍历顺序从后往前从前往后原因每个物品只能选一次避免重复使用每个物品可以选多次允许重复使用核心代码for j in range(W, w[i]-1, -1)for j in range(w[i], W1)六、动态规划解题思路总结通过以上四个案例我们可以总结出动态规划的通用解题步骤1. 确定状态问自己问题可以分解为哪些子问题状态通常用一维或二维数组表示状态要能准确描述子问题的解2. 写出状态转移方程思考当前状态与之前状态的关系这是DP问题最难也是最核心的一步通常需要考虑“选择”或“不选择”两种可能性3. 确定边界条件最小的子问题是什么如何初始化比如爬楼梯的f(1)1, f(2)24. 确定遍历顺序自顶向下递归记忆化还是自底向上迭代如果使用迭代需要保证计算当前状态时依赖的状态已经计算完毕5. 优化空间观察递推关系看能否用滚动数组或一维数组优化空间七、常见动态规划题型分类线性DP爬楼梯、最大子数组和背包问题0-1背包、完全背包、多重背包区间DP石子合并、最长回文子序列树形DP树上的最大独立集状态压缩DP旅行商问题数位DP数字统计类问题八、结语动态规划的精髓在于用空间换时间——通过存储子问题的解来避免重复计算。初学者往往觉得DP难是因为没有建立起正确的思考方式。记住这三点DP不再难定义好状态状态定义决定了问题的表达方式找出递推关系当前状态如何从之前的状态推导出来确定边界和顺序从哪里开始按什么顺序计算实践是掌握动态规划的最好方法。建议你在LeetCode上按照题型分类练习每道题都要真正理解其状态定义和转移方程而不是死记硬背代码。当你做够一定数量的DP题目后你会发现看似千变万化的问题其核心思想其实是相通的。希望这篇文章能帮助你打开动态规划的大门在算法学习的道路上更进一步思考题如果爬楼梯可以爬1、2、3阶该如何修改状态转移方程如果每阶台阶有不同的代价求最小代价到达楼顶又该如何解决