TECH ARTICLES
算法动态规划LeetCode

动态规划深度解析：从"傻递归"到"空间魔术师"的进化之路

Jackie Zhan2026-07-05
目录
一、从一个问题说起 二、DP 的四要素：一个都不能少 三、入门第一关：斐波那契数列 四、经典战役：背包问题 五、经典双子星：LCS 与 LIS 六、最烧脑挑战：编辑距离 七、终极奥义：空间优化 八、实战路线图

一、从一个问题说起

上周有个朋友给我发了条消息：

"动态规划？不就是把递归结果存起来吗，这有什么好讲的？"
——我那位"以为懂了但其实没懂"的朋友

我问他："那你说，编辑距离怎么用动态规划解？"
他沉默了三分钟，发了个表情包。

动态规划（Dynamic Programming，简称 DP）大概是算法世界里被误解最深的概念。每个人都觉得自己会用，但面试的时候一提"空间优化"就卡壳，一遇到"股票买卖"就崩溃。

这篇文章，就是要让这种尴尬消失。我们不只讲"是什么"，更要讲透"为什么这么想"。看完之后，你对 DP 的理解会从"会用"升级到"能教别人"的程度。

顺便说一句，这是算法入门系列的第二篇。第一篇我们聊了算法的宇宙观和复杂度分析，如果还没读过，建议先收藏这篇，然后回去补补课。

二、DP 的四要素：一个都不能少

动态规划的本质是什么？我的定义是：把一个复杂问题拆成互相重叠的子问题，只算一次，记录答案，然后用它算出更大问题的答案。

听起来简单，但真正的高手和普通人的差距，藏在四个关键决策里。

要素一：状态定义——这是最难的一步

状态，就是你用什么样的"视角"去描述问题。选对了状态，问题就解了一半；选错了状态，你可能写到两百行还跑不通。

举个例子。背包问题的状态怎么定义？

菜鸟的思路："状态就是第 i 个物品选不选"——这个描述的是动作，不是问题的数学状态。

高手的思路：dp[i][j] = 考虑前 i 个物品，容量为 j 的背包能装的最大价值。这就是状态。

实战案例
状态定义没有标准答案，但有一个检验标准：你的状态能不能推导出最终答案？ 如果状态定义完之后，你发现从它到问题答案还需要绕很多弯，那大概率定义得不够本质。

要素二：状态转移方程——DP 的灵魂

如果说状态是地基，那状态转移方程就是连接每个房间的楼梯。它描述的是：已知小问题的答案，如何得到大问题的答案。

写状态转移方程的核心思路就一句话：新问题 = 选或不选 + 子问题的答案

以斐波那契为例：dp[n] = dp[n-1] + dp[n-2]。第 n 项的值，取决于前面两个子问题的答案相加。

要素三：初始化——万丈高楼从哪起

状态转移方程是递推公式，它需要一个或多个"已知真相"作为起点。这个起点就是初始化。

斐波那契的初始化是 dp[0] = 0, dp[1] = 1。如果初始化错了，整个 DP 都会歪掉。

要素四：遍历顺序——顺序不对，全盘皆错

动态规划的遍历顺序必须满足一个条件：计算每个状态时，它依赖的所有子状态都已经被计算完了。

DP 解题四步法与实现路径对比 ① 状态定义 选视角描述问题 ② 状态转移 子问题推大问题 ③ 初始化 递推的起点 ④ 遍历顺序 保证依赖已计算 答案 ✓ 暴力递归 同一子问题算 N 次 → O(2^n) 记忆化递归 HashMap 缓存 → O(n) 自底向上 DP 循环取代递归 → 更稳更快 空间优化 只存需要的 → O(1) 核心思想：把重叠子问题的结果存起来，只算一次
DP 核心四要素与三种实现路径对比

这四个要素搞清楚了，你对 DP 的理解就已经超过 80% 的面试者了。接下来，我们用经典问题把它们一一落地。

三、入门第一关：斐波那契数列

很多人觉得斐波那契太简单了，不值得讲。但我的观点正好相反——越是简单的问题，越藏着最本质的洞见。

从暴力递归到 DP 的完整进化

先看暴力递归版本：

# ❌ 暴力递归：时间 O(2^n)，空间 O(n) 递归栈
def fib1(n):
    if n <= 1:
        return n
    return fib1(n-1) + fib1(n-2)

这个版本的问题在哪？画一下递归树你就知道了——fib(4) 被算了一次，fib(3) 被算了两次，fib(2) 被算了三次……指数爆炸。

常见误区
斐波那契递归的问题不是"递归太慢"，而是"重复计算"。同样一个子问题，被算了指数级别那么多遍。如果只是慢在递归调用次数，那还好；慢在重复算同样的东西，这才是真正要优化的点。

加上记忆化，把算过的结果存起来：

# ✅ 记忆化递归：时间 O(n)，空间 O(n)
from functools import lru_cache

@lru_cache(maxsize=None)
def fib2(n):
    if n <= 1:
        return n
    return fib2(n-1) + fib2(n-2)

改成自底向上的 DP，消除递归栈：

# ✅ 自底向上 DP：时间 O(n)，空间 O(n)
def fib3(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

到这里，很多教程就停了。但我要再进一步——这就是空间优化的起点。

空间优化：一维到两个变量

你注意到没有？在 fib3 的循环里，dp[i] 只依赖 dp[i-1] 和 dp[i-2]。换句话说，我不需要存整个数组，只需要记住最近的两个值就够了。

# ✅ 空间优化版：时间 O(n)，空间 O(1)
def fib4(n):
    if n <= 1:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

从 O(n) 空间压缩到 O(1) 空间，这个技巧叫滚动数组。斐波那契这一关，藏着整个 DP 空间优化的核心思想——只保留真正需要的那些状态。

insider 视角
面试官问斐波那契，通常醉翁之意不在酒。他真正想看的是：你能不能意识到从递归到记忆化到 DP 再到空间优化的完整进化路径。直接写出 O(1) 空间的版本不难，难的是你能讲清楚"为什么 O(n) 空间可以优化成 O(1)"。

四、经典战役：背包问题

如果说斐波那契是 DP 的热身，那背包问题就是 DP 的主战场。面试中出现频率极高，而且变体极多——0-1 背包、完全背包、多维背包……但只要掌握了核心思想，万变不离其宗。

0-1 背包：每个物品只能选一次

问题定义：有 n 件物品，每件物品有重量 w[i] 和价值 v[i]，背包容量为 C，求不超过容量能装下的最大价值。

状态定义：dp[i][j] = 考虑前 i 件物品，背包容量为 j 时能获得的最大价值。

状态转移：对于第 i-1 件物品，选或不选，取价值更大的那个。

def knapsack_01(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        w, v = weights[i-1], values[i-1]
        for j in range(capacity + 1):
            dp[i][j] = dp[i-1][j]          # 不选
            if j >= w:
                dp[i][j] = max(dp[i][j], dp[i-1][j-w] + v)  # 选
    return dp[n][capacity]

这段代码里，关键在第 8 行：dp[i-1][j-w] 指的是"考虑前 i-1 件物品、容量减少 w 之后的最大价值"，再加上当前物品的价值 v，就是选这件物品的总价值。

0-1 背包 DP 表（w=[2,3,4,5], v=[3,4,5,6], C=8） i\j 012345678 0 000000000 1 003333333 2 003447777 3 003457899 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v) i=2, w=3, v=4, j=5: dp[2][5] = max(dp[1][5]=3, dp[1][2]+4=7) → 选物品2（w=3），价值7 i=3, w=4, v=5, j=8: dp[3][8] = max(dp[2][8]=7, dp[2][4]+5=9) → 选物品3（w=4），价值9
0-1 背包 DP 表：每行只依赖上一行，高亮为该行新增/更新的值

注意表格中一个关键规律：第 i 行只依赖第 i-1 行。这意味着我们不需要保存整个二维数组，用一行就够了。

# ✅ 空间优化版：时间 O(n*C)，空间 O(C)
def knapsack_01_optimized(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        # ⚠️ 必须倒序遍历容量！
        for j in range(capacity, w - 1, -1):
            dp[j] = max(dp[j], dp[j-w] + v)
    return dp[capacity]

这里有个极其容易出错的地方：容量必须倒序遍历。为什么？如果正序遍历，dp[j-w] 已经被当前物品更新过了（相当于一个物品选了两次），而倒序遍历保证每次都用上一行的旧值。

踩坑记录
for j in range(w, capacity + 1): 是错的，for j in range(capacity, w - 1, -1): 才是对的。这个坑我见过无数人面试时踩进去——包括我自己当年。

完全背包：物品无限选

和 0-1 背包的唯一区别：每件物品可以选无限次。解决方案就是容量遍历方向反过来——正序，因为正序时 dp[j-w] 已经被当前物品更新过，正好代表"选了若干件当前物品"的情况。

# ✅ 完全背包：时间 O(n*C)，空间 O(C)
def knapsack_complete(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for j in range(w, capacity + 1):  # 正序！
            dp[j] = max(dp[j], dp[j-w] + v)
    return dp[capacity]

一个遍历方向的差异，决定了 0-1 背包还是完全背包。魔鬼藏在细节里。

五、经典双子星：LCS 与 LIS

两个字符串/序列的问题，是 DP 的另一大王牌领域。

最长公共子序列（LCS）

问题定义：给定两个字符串，求它们的最长公共子序列（Subsequence，不要求连续）的长度。

这个问题的应用场景极其广泛：diff 工具（比较两个文件差异）、生物信息学（DNA 序列比对）、文本查重……

状态定义：dp[i][j] = 字符串 A 的前 i 个字符和字符串 B 的前 j 个字符的最长公共子序列长度。

状态转移：

def lcs(s1, s2):
    n, m = len(s1), len(s2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[n][m]

# 示例：lcs("abcde", "ace") = 3 ("ace")
# 示例：lcs("abcabc", "defabc") = 3 ("abc")

这里有个特别有意思的地方：dp[i][j] 要么等于 dp[i-1][j-1] + 1（当前字符匹配上了），要么等于 dp[i-1][j] 或 dp[i][j-1]（至少有一个字符串的最后一个字符不参与匹配）。这个决策逻辑本身就是一种"分治"——要么匹配这两个字符，要么放弃其中一个。

LCS 状态转移（s1="ABCD", s2="AEBD"） i\j 0AEBD 0 00000 A 001111 B 001122 C 001122 D 001123 s1[i-1]==s2[j-1]? "A"=="A" → dp[i][j] = dp[i-1][j-1]+1 "B"=="E" → 不等，取 max(dp[i-1][j], dp[i][j-1]) LCS = "ABD"，长度 3 s1[3]="D" == s2[4]="D" → 匹配！ dp[4][5] = dp[3][4] + 1 = 2 + 1 = 3 "D" 在两串中都出现，且是最后一个匹配的字符
LCS DP 表：匹配字符对角线推进，不匹配时取上/左最大值

最长递增子序列（LIS）

问题定义：给定一个序列，找出其中最长的递增子序列的长度。Subsequence 可以不连续，但顺序必须保持。

状态定义：dp[i] = 以第 i 个元素结尾的最长递增子序列长度。

状态转移：遍历所有在 i 之前的元素 j，如果 nums[j] < nums[i]，说明可以把 nums[i] 接在以 nums[j] 结尾的递增序列后面。

# ✅ LIS：时间 O(n^2)，空间 O(n)
def lis(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[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

# 示例：lis([10,9,2,5,3,7,101,18]) = 4（[2,3,7,101] 或 [2,3,7,18]）

这个 O(n^2) 的版本好理解，但面试官通常还会追问：有没有更快的做法？答案是二分查找优化，把时间复杂度降到 O(n log n)，这就是传说中的"贪心 + 二分"解法。

# ✅ LIS 二分优化：时间 O(n log n)，空间 O(n)
import bisect

def lis_binary(nums):
    d = []  # d[i] = 长度为 i+1 的递增子序列的最小结尾元素
    for x in nums:
        i = bisect.bisect_left(d, x)  # 找第一个 >= x 的位置
        if i == len(d):
            d.append(x)   # x 比所有元素都大，可以延长序列
        else:
            d[i] = x      # 用更小的 x 替换，保持 d 的最小性
    return len(d)

二分优化的核心思想是：维护一个数组 d，其中 d[i] 表示长度为 i+1 的递增子序列的最小可能结尾值。这个数组是严格递增的，所以可以用二分查找。对于每个新元素，找到它在 d 中的位置——要么延长最长序列，要么用更小的值替换，让后续元素有更大的可能性接上来。

对比一下
O(n^2) 的 DP 版本好理解，适合面试时先写出来证明思路正确；O(n log n) 的二分版本展示了你对算法优化的追求。两个都要会。

六、最烧脑挑战：编辑距离

编辑距离是 LeetCode 上的 Hard 级别问题，也是面试官的最爱。它把 DP 的状态定义能力压榨到了极限。

问题定义：给定两个字符串 word1 和 word2，通过插入、删除、替换三种操作，把 word1 变成 word2 的最少步数。

状态定义：dp[i][j] = word1 的前 i 个字符变成 word2 的前 j 个字符所需的最少操作数。

状态转移（最烧脑的部分）：

def edit_distance(word1, word2):
    n, m = len(word1), len(word2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    # 初始化：第一行/列
    for i in range(n + 1):
        dp[i][0] = i  # word1 前 i 个字符变成空串，需要 i 次删除
    for j in range(m + 1):
        dp[0][j] = j  # 空串变成 word2 前 j 个字符，需要 j 次插入
    
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
    
    return dp[n][m]

# 示例：edit_distance("horse", "ros") = 3
# horse → ros（删除 h, 删除 e, 删除 e）或者替换 r→r, o→o, s→s 等多种路径
编辑距离 DP 表（word1="horse", word2="ros"） i\j 0ros 0 0123 h 1112 o 2212 r 3222 s 4332 e 5443 dp[i][j] = dp[i-1][j-1]（匹配） 或 1 + min(替换, 删除, 插入) horse → ros 的最少操作数 = 3 dp[5][3] = 3 horse 删除 h → orse（1步） orse 删除 e → ors（1步） ors 删除 r？不对，应该是： horse 的 r 匹配 ros 的 r（0步） horse 的 o 匹配 ros 的 o（0步） horse 的 s 匹配 ros 的 s（0步） horse 删除 h、e、e → ros（3步）✓
编辑距离 DP 表：结果 dp[5][3] = 3，三种操作取最优

编辑距离的难点在于：三种操作的物理含义要理解清楚——替换是"改"，删除是"少一个"，插入是"多一个"。理解了操作本质，状态转移方程就不难写出来。

七、终极奥义：空间优化

前面我们已经见过很多空间优化的例子了（斐波那契、背包）。现在我们来系统地总结一下空间优化的通用技巧。

技巧一：滚动数组——只保留必要的行

如果 dp[i][j] 只依赖 dp[i-1][*]（即当前行只依赖上一行），那么我们只需要维护一维数组。

0-1 背包和完全背包的优化就是这个原理。

技巧二：状态压缩到极致

如果一维数组中，每个位置只依赖它左边的某个位置（比如 dp[j] = max(dp[j], dp[j-w] + v)），那么这个 j 的遍历方向就决定了是 0-1 背包（倒序）还是完全背包（正序）。

技巧三：两个变量代替整个数组

斐波那契就是最经典的例子。当 dp[i] 只依赖 dp[i-1] 和 dp[i-2] 时，用 prev 和 curr 两个变量就够了。

# 斐波那契：两个变量
prev, curr = 0, 1
for _ in range(2, n + 1):
    prev, curr = curr, prev + curr

# LCS：两行交替
prev = [0] * (m + 1)
curr = [0] * (m + 1)
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if s1[i-1] == s2[j-1]:
            curr[j] = prev[j-1] + 1
        else:
            curr[j] = max(prev[j], curr[j-1])
    prev, curr = curr, [0] * (m + 1)

空间优化的取舍

空间优化虽好，但要注意场景：

一句话记住
空间优化是锦上添花，不是必须追求的目标。先保证正确性和可读性，再考虑优化。面试时先写二维版本，再优化成一维，是个很好的展示思路的方式。

八、实战路线图

聊了这么多，最后给你一个可操作的练习路线。

必刷经典题（按难度排序）

题目LeetCode核心技巧难度
爬楼梯#70斐波那契变体⭐
打家劫舍#198一维 DP，空间优化⭐
不同路径#62二维 DP 入门⭐⭐
三角形最小路径和#120自底向上 DP⭐⭐
最长递增子序列#300DP + 二分优化⭐⭐
最长公共子序列#1143双串 DP⭐⭐
编辑距离#72三操作 DP⭐⭐⭐
背包问题#416 等状态定义 + 空间优化⭐⭐⭐
股票买卖#121-123, 188状态机 DP⭐⭐⭐

我的学习建议

  1. 先理解四要素：状态定义、状态转移、初始化、遍历顺序。这四个搞清楚了，任何 DP 题都能有思路
  2. 从简单题入手：爬楼梯、打家劫舍都是斐波那契的变体，先把这些做熟建立信心
  3. 画表理解：拿到题先在纸上画 DP 表，比直接写代码更能理解状态转移
  4. 先二维后优化：面试时先写二维数组确保正确，再优化空间展示能力
  5. 反复咀嚼经典题：LCS、编辑距离、背包刷三遍，每遍都有新收获

我认为：动态规划不是一种"算法模板"，而是一种"思维方式"。它教会你的不只是怎么解题，更是怎么把一个大问题分解成小问题、如何找到问题的最小视角。这种能力，才是 DP 真正给你的礼物。

下一步建议：打开 LeetCode，从 #70 爬楼梯开始，把上面的必刷题列表刷完。刷完之后，你对 DP 的理解会彻底不同。

最后留个小彩蛋：斐波那契数列有个鲜为人知的秘密——它的时间复杂度其实可以用矩阵快速幂优化到 O(log n)。如果你的面试官特别"变态"，可能会问到这个。提示：斐波那契矩阵形式是 [[1,1],[1,0]] 的 n 次幂。有兴趣的话去研究一下。

参考资料

  1. LeetCode 动态规划题目列表
  2. 极客时间《算法面试通关40讲》
  3. Dynamic Programming - Wikipedia