Python算法基础篇之动态规划

写在前面

说实话，我第一次接触动态规划（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):ifn<=1: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 记忆化搜索：给递归加个缓存

这就是动态规划的第一种实现方式——记忆化搜索（也叫自顶向下的 DP）：

fromfunctoolsimportlru_cache@lru_cache(maxsize=None)deffib_memo(n):ifn<=1:returnnreturnfib_memo(n-1)+fib_memo(n-2)

或者手动用字典实现：

deffib_memo_manual(n,memo=None):ifmemoisNone:memo={}ifninmemo:returnmemo[n]ifn<=1: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):ifn<=1:returnn dp=[0]*(n+1)dp[0]=0dp[1]=1foriinrange(2,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]

1.4 三种写法性能对比

从图上可以明显看到，纯递归在 n=35 的时候就已经慢到没法用了，而 DP 和记忆化搜索都是线性增长。

二、动态规划的核心要素

我总结了一个五步解题法，做题的时候按这个套路来：

2.1 第一步：定义状态

dp[i]或dp[i][j]到底代表什么？这个定义必须清晰、无歧义。定义错了，后面全白搭。

2.2 第二步：找状态转移方程

状态转移方程是 DP 的灵魂，描述了大问题和小问题之间的关系。斐波那契里就是dp[i] = dp[i-1] + dp[i-2]。

2.3 第三步：初始化边界条件

DP 是从底向上推的，最底层的基础值必须手动设置好。比如dp[0] = 0，dp[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):ifn<=2:returnn dp=[0]*(n+1)dp[1]=1dp[2]=2foriinrange(3,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]

空间优化到 O(1)：

defclimbStairs_optimized(n):ifn<=2:returnn prev2,prev1=1,2foriinrange(3,n+1):curr=prev1+prev2 prev2=prev1 prev1=currreturnprev1

3.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):n=len(weights)dp=[[0]*(W+1)for_inrange(n+1)]foriinrange(1,n+1):forwinrange(1,W+1):dp[i][w]=dp[i-1][w]ifw>=weights[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]W=8print(knapsack(weights,values,W))# 输出: 9

一维空间优化（内层必须从后往前遍历）：

defknapsack_1d(weights,values,W):dp=[0]*(W+1)foriinrange(len(weights)):forwinrange(W,weights[i]-1,-1):dp[w]=max(dp[w],values[i]+dp[w-weights[i]])returndp[W]

3.3 最长公共子序列（LCS，LeetCode 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,n=len(text1),len(text2)dp=[[0]*(n+1)for_inrange(m+1)]foriinrange(1,m+1):forjinrange(1,n+1):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)
• 转移方程难找：有些问题的转移方程非常巧妙

五、常见坑和注意事项

1. 边界条件初始化不对：直接影响整个 DP 表格，一定要仔细推敲
2. 遍历顺序搞反了：背包一维优化必须从后往前，否则变成完全背包
3. 状态定义不够清晰：是前 i 个还是以第 i 个结尾？定义不同结果不同
4. 空间优化过度导致代码难读：面试先写二维版本，再谈优化

总结

动态规划说白了就一句话：把大问题拆成小问题，记住小问题的答案，用它们拼出大问题的答案。

记住这五步：定义状态 -> 找转移方程 -> 初始化边界 -> 确定遍历顺序 -> 返回结果。

刚开始学的时候，每道题都在纸上画一下 DP 表格，手动填几个值，比干想有效得多。等你刷到 20 道左右的 DP 题，基本就能一眼看出状态定义了。

DP 没有捷径，唯手熟尔。多写、多画、多总结，你一定能搞定它。

如果这篇文章对你有帮助，欢迎点赞收藏！有任何问题可以在评论区留言，我会尽量回复。