写在前面说实话我第一次接触动态规划Dynamic Programming简称 DP的时候整个人是懵的。什么最优子结构、重叠子问题、状态转移方程……这些名词听起来就很劝退。后来刷了不少题踩了很多坑才慢慢摸到了一点门道。这篇文章不会跟你讲那些让人头大的数学证明而是用最接地气的方式带你从 0 到 1 搞懂动态规划。我会用大量图解和实际代码把 DP 的核心思想掰开了揉碎了讲清楚。看完这篇至少 LeetCode 上那些经典的 DP 题目你应该能独立做出来了。好了废话不多说咱们开始吧。一、动态规划到底是什么先别急着看定义我们从一个最经典的例子入手——斐波那契数列。1.1 斐波那契数列的递归写法斐波那契数列的定义很简单F(0) 0 F(1) 1 F(n) F(n-1) F(n-2) (n 2)用递归写起来非常直观deffib(n):ifn1:returnnreturnfib(n-1)fib(n-2)这代码看起来挺优雅的对吧但你试着算一下fib(35)电脑风扇立马狂转。为什么因为这里面存在大量的重复计算。我用一张图给你看看fib(5)的递归调用过程你就明白了看到没f(3)被算了 2 次f(2)被算了 3 次f(1)更是被算了 5 次这些重复计算就像滚雪球一样随着 n 增大计算量呈指数级爆炸。时间复杂度是O(2^n)简直慢得离谱。那怎么办很简单把算过的结果存起来下次直接查表不就行了1.2 记忆化搜索给递归加个缓存这就是动态规划的第一种实现方式——记忆化搜索也叫自顶向下的 DPfromfunctoolsimportlru_cachelru_cache(maxsizeNone)deffib_memo(n):ifn1:returnnreturnfib_memo(n-1)fib_memo(n-2)或者手动用字典实现deffib_memo_manual(n,memoNone):ifmemoisNone:memo{}ifninmemo:returnmemo[n]ifn1:returnn memo[n]fib_memo_manual(n-1,memo)fib_memo_manual(n-2,memo)returnmemo[n]加了缓存之后每个f(n)只会被计算一次。时间复杂度一下子降到了O(n)空间复杂度也是O(n)。1.3 动态规划自底向上填表记忆化搜索虽然好但它本质上还是递归递归有栈深度的限制。于是就有了 DP 的第二种实现方式——自底向上填表deffib_dp(n):ifn1:returnn dp[0]*(n1)dp[0]0dp[1]1foriinrange(2,n1):dp[i]dp[i-1]dp[i-2]returndp[n]1.4 三种写法性能对比从图上可以明显看到纯递归在 n35 的时候就已经慢到没法用了而 DP 和记忆化搜索都是线性增长。二、动态规划的核心要素我总结了一个五步解题法做题的时候按这个套路来2.1 第一步定义状态dp[i]或dp[i][j]到底代表什么这个定义必须清晰、无歧义。定义错了后面全白搭。2.2 第二步找状态转移方程状态转移方程是 DP 的灵魂描述了大问题和小问题之间的关系。斐波那契里就是dp[i] dp[i-1] dp[i-2]。2.3 第三步初始化边界条件DP 是从底向上推的最底层的基础值必须手动设置好。比如dp[0] 0dp[1] 1。2.4 第四步确定遍历顺序填表是有顺序的。要确保在计算dp[i]的时候dp[i-1]和dp[i-2]已经算好了。2.5 第五步返回最终结果根据题目要求返回dp[n]或dp[m][n]之类的值。三、经典例题详解3.1 爬楼梯问题LeetCode 70题目假设你正在爬楼梯需要 n 阶才能到达楼顶。每次你可以爬 1 阶或 2 阶问有多少种不同的方法代码实现defclimbStairs(n):ifn2:returnn dp[0]*(n1)dp[1]1dp[2]2foriinrange(3,n1):dp[i]dp[i-1]dp[i-2]returndp[n]空间优化到 O(1)defclimbStairs_optimized(n):ifn2:returnn prev2,prev11,2foriinrange(3,n1):currprev1prev2 prev2prev1 prev1currreturnprev13.2 0/1 背包问题题目有 n 个物品重量 weight[i]价值 value[i]。背包容量 W每个物品只能选一次求最大总价值。状态定义dp[i][w] 前 i 个物品容量 w 时的最大价值状态转移方程dp[i][w] max(dp[i-1][w], value[i] dp[i-1][w-weight[i]]) (if w weight[i]) dp[i][w] dp[i-1][w] (if w weight[i])完整代码defknapsack(weights,values,W):nlen(weights)dp[[0]*(W1)for_inrange(n1)]foriinrange(1,n1):forwinrange(1,W1):dp[i][w]dp[i-1][w]ifwweights[i-1]:dp[i][w]max(dp[i][w],values[i-1]dp[i-1][w-weights[i-1]])returndp[n][W]weights[2,3,4,5]values[3,4,5,6]W8print(knapsack(weights,values,W))# 输出: 9一维空间优化内层必须从后往前遍历defknapsack_1d(weights,values,W):dp[0]*(W1)foriinrange(len(weights)):forwinrange(W,weights[i]-1,-1):dp[w]max(dp[w],values[i]dp[w-weights[i]])returndp[W]3.3 最长公共子序列LCSLeetCode 1143题目给定两个字符串返回它们的最长公共子序列的长度。状态定义dp[i][j] text1 前 i 个字符和 text2 前 j 个字符的 LCS 长度状态转移方程如果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])完整代码deflongestCommonSubsequence(text1,text2):m,nlen(text1),len(text2)dp[[0]*(n1)for_inrange(m1)]foriinrange(1,m1):forjinrange(1,n1):iftext1[i-1]text2[j-1]:dp[i][j]dp[i-1][j-1]1else:dp[i][j]max(dp[i-1][j],dp[i][j-1])returndp[m][n]print(longestCommonSubsequence(abcde,ace))# 输出: 3四、动态规划的优缺点优点效率高避免重复计算指数级降到多项式级思路清晰找到状态定义和转移方程后代码很规整适用范围广最优化、计数、可行性问题都能用缺点状态定义难定义错了后面全崩空间开销大二维 DP 可能是 O(n^2)转移方程难找有些问题的转移方程非常巧妙五、常见坑和注意事项边界条件初始化不对直接影响整个 DP 表格一定要仔细推敲遍历顺序搞反了背包一维优化必须从后往前否则变成完全背包状态定义不够清晰是前 i 个还是以第 i 个结尾定义不同结果不同空间优化过度导致代码难读面试先写二维版本再谈优化总结动态规划说白了就一句话把大问题拆成小问题记住小问题的答案用它们拼出大问题的答案。记住这五步定义状态 - 找转移方程 - 初始化边界 - 确定遍历顺序 - 返回结果。刚开始学的时候每道题都在纸上画一下 DP 表格手动填几个值比干想有效得多。等你刷到 20 道左右的 DP 题基本就能一眼看出状态定义了。DP 没有捷径唯手熟尔。多写、多画、多总结你一定能搞定它。如果这篇文章对你有帮助欢迎点赞收藏有任何问题可以在评论区留言我会尽量回复。