从算法到人工智能 · 第 17 课：动态规划——用空间换时间

先看一个经典问题：爬楼梯。每次可以走 1 级或 2 级，问爬到第 n 级有多少种走法？

一个直觉的解法是递归（第 9 课学过）：

def climb(n):
    if n <= 2:
        return n
    return climb(n-1) + climb(n-2)

print(climb(5))   # 8

看着很优雅，但它有个致命问题：大量重复计算。算 climb(5) 时，climb(3) 被算了好几次，climb(2) 更是被算了无数次。当 n 到 40，这个递归已经慢到要等很久。

动态规划（Dynamic Programming，DP），就是来解决这个问题的：把算过的结果存下来，用空间换时间，避免重复计算。

一、DP 的核心思想：记住算过的，别重复算

递归版为什么慢？因为它"算了又算"。DP 的答案很简单——用一个数组（或字典）把已经算过的结果记下来，下次直接用。

def climb(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)   # dp[i] = 爬到第 i 级的方法数
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]   # 状态转移
    return dp[n]

print(climb(40))   # 165580141，瞬间出结果

对比一下：递归版 climb(40) 要算 3 亿多次，DP 版只算 40 次循环。这就是"用空间换时间"的力量。

二、DP 的两个关键：状态 + 转移

DP 题千变万化，但套路只有两个核心：

1. 定义"状态"（用数组表示什么）

dp[i] 到底代表什么？这是 DP 最难的、也是最重要的一步。

爬楼梯里：dp[i] = "爬到第 i 级的方法数"。

2. 找到"状态转移方程"（怎么从已知推出未知）

dp[i] 和 dp[i-1]、dp[i-2] 有什么关系？

爬楼梯里：到第 i 级，要么从 i-1 级走 1 步，要么从 i-2 级走 2 步，所以 dp[i] = dp[i-1] + dp[i-2]。

记住这个口诀：先想清楚 dp 数组表示什么，再想清楚 dp[i] 从谁转移来。

三、DP 的两种写法

1. 自底向上（迭代，最常用）

从小到大依次填表。上面爬楼梯的循环就是这种。推荐先用这种，因为它省内存、不会栈溢出。

2. 自顶向下（记忆化搜索，递归 + 备忘录）

保留递归的结构，但用一个字典记住算过的结果：

def climb_memo(n, memo={}):
    if n <= 2:
        return n
    if n not in memo:               # 没算过才递归
        memo[n] = climb_memo(n-1, memo) + climb_memo(n-2, memo)
    return memo[n]                  # 算过直接返回

print(climb_memo(40))

记忆化搜索 = 递归 + 备忘录。它更容易写（直接从递归翻译过来），但递归深度大了会栈溢出。

四、经典 DP 问题

1. 爬楼梯（入门）

上面已经讲了。这是"斐波那契数列"的变体，DP 的 hello world。

2. 最大子数组和（面试高频）

给你一个数组，找连续子数组的最大和。

状态：dp[i] = "以第 i 个元素结尾的最大子数组和"。
转移：要么延续前面的（dp[i-1] + nums[i]），要么重新开始（nums[i]），取大的。

def max_subarray(nums):
    dp = [0] * len(nums)
    dp[0] = nums[0]
    for i in range(1, len(nums)):
        dp[i] = max(nums[i], dp[i-1] + nums[i])
    return max(dp)

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray(nums))   # 6（子数组 [4,-1,2,1]）

3. 0-1 背包问题（DP 的招牌）

有 n 件物品，每件有重量和价值，背包容量有限，问怎么装价值最大。每件物品要么拿（1）要么不拿（0）。

状态：dp[i][w] = "前 i 件物品、背包容量为 w 时的最大价值"。
转移：第 i 件物品，要么不装（dp[i-1][w]），要么装（dp[i-1][w-weight[i]] + value[i]），取大的。

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i-1] > w:      # 装不下，只能不装
                dp[i][w] = dp[i-1][w]
            else:                     # 装 or 不装，取大的
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1])
    return dp[n][capacity]

weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
print(knapsack(weights, values, 8))   # 10（拿 3+5 → 价值 4+6=10）

4. 最长公共子序列（LCS）

给两个字符串，找它们最长的公共子序列（不要求连续）。

状态：dp[i][j] = "text1 前 i 个字符和 text2 前 j 个字符的最长公共子序列长度"。
转移：末尾字符相等则 dp[i-1][j-1]+1，不相等则取 max(dp[i-1][j], dp[i][j-1])。

def lcs(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            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])
    return dp[m][n]

print(lcs("abcde", "ace"))   # 3（"ace"）

更多经典：编辑距离与最长递增子序列

DP 的应用远不止上面三个，这里再补两个面试超高频的，感受一下"状态怎么设计"。

① 编辑距离（Levenshtein）：把字符串 A 变成 B，最少需要几次"增、删、改"？这是拼写检查、diff 对比、DNA 比对的底层算法。

状态：dp[i][j] = 把 a 的前 i 个字符变成 b 的前 j 个字符的最少操作数。

def edit_dist(a, b):
    dp = [[0] * (len(b)+1) for _ in range(len(a)+1)]
    for i in range(len(a)+1): dp[i][0] = i   # 删掉 i 个
    for j in range(len(b)+1): dp[0][j] = j   # 插入 j 个
    for i in range(1, len(a)+1):
        for j in range(1, len(b)+1):
            dp[i][j] = min(
                dp[i-1][j] + 1,          # 删
                dp[i][j-1] + 1,          # 增
                dp[i-1][j-1] + (a[i-1] != b[j-1])  # 改（相同则不改）
            )
    return dp[-1][-1]

print(edit_dist("horse", "ros"))   # 3

② 最长递增子序列（LIS）：找数组里"严格递增、可跳着取"的最长子序列长度。经典 O(n²) DP。

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

def lis(a):
    dp = [1] * len(a)
    for i in range(len(a)):
        for j in range(i):
            if a[j] < a[i]:              # 能接在 a[j] 后面
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

print(lis([10, 9, 2, 5, 3, 7, 101, 18]))   # 4（2,3,7,101）

这两个题的共同点："最优子结构"藏在"结尾/前缀"里——想清楚"状态代表什么"，转移就顺了。

五、DP 的两大特性（怎么判断能用 DP）

最优子结构：大问题的最优解，能由子问题的最优解推出。
重叠子问题：子问题会被重复计算（这正是 DP 要解决的）。

有这两条，就能用 DP。这也是 DP 和贪心（第 16 课）的区别：贪心要求"每一步选最优就不用回头"，DP 则是"把每个子问题的最优都记下来，最后综合"。贪心更快但适用范围窄，DP 更通用但费空间。

六、空间优化：滚动数组

很多时候，dp[i] 只依赖 dp[i-1] 和 dp[i-2]，前面的都不用留。这时可以只存最近几个值，把空间从 O(n) 降到 O(1)。

爬楼梯的空间优化版：

def climb_opt(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b   # a=dp[i-2], b=dp[i-1]
    return b

print(climb_opt(40))

体会：DP 的数组往往可以"瘦身"成几个变量，这是常考的优化点。

七、复杂度小结

问题	时间复杂度	空间复杂度
爬楼梯（DP）	O(n)	O(n)（可优化到 O(1)）
最大子数组和	O(n)	O(n)（可优化到 O(1)）
0-1 背包	O(n × W)	O(n × W)（可优化到 O(W)）
最长公共子序列	O(m × n)	O(m × n)

八、动手时间 🎯

实验 1：感受递归 vs DP 的差距

import time

def climb_rec(n):
    if n <= 2:
        return n
    return climb_rec(n-1) + climb_rec(n-2)

def climb_dp(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

n = 35
start = time.time(); r1 = climb_rec(n); t1 = time.time() - start
start = time.time(); r2 = climb_dp(n); t2 = time.time() - start
print(f"递归: {round(t1,4)}s | DP: {round(t2,6)}s | 结果一致: {r1 == r2}")

体会：n=35 时递归可能要 1~2 秒，DP 是微秒级。差距是数量级的。

实验 2：打印最大子数组的"哪个子数组"

def max_subarray_with_range(nums):
    dp = [0] * len(nums)
    dp[0] = nums[0]
    for i in range(1, len(nums)):
        dp[i] = max(nums[i], dp[i-1] + nums[i])
    best_end = dp.index(max(dp))
    # 从 best_end 往前找起点
    total, best_start = 0, best_end
    for i in range(best_end, -1, -1):
        total += nums[i]
        if total == max(dp):
            best_start = i
            break
    return nums[best_start:best_end+1], max(dp)

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
sub, s = max_subarray_with_range(nums)
print("子数组:", sub, "和:", s)   # [4,-1,2,1] 和 6

实验 3：背包问题——看装了什么

def knapsack_with_items(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i-1] > w:
                dp[i][w] = dp[i-1][w]
            else:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1])
    # 回溯选中的物品
    w = capacity
    picked = []
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i-1][w]:      # 说明第 i 件被选中
            picked.append(i-1)
            w -= weights[i-1]
    return dp[n][capacity], picked

weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
v, picked = knapsack_with_items(weights, values, 8)
print("最大价值:", v, "选中物品下标:", picked)   # 10, [3,1] → 5 和 3

实验 4（挑战）：零钱兑换（最少硬币数）

给一堆硬币面额和一个金额，求凑出该金额的最少硬币数（可重复用）。这是 DP 的经典题，注意和贪心不同——DP 保证最优。

def coin_change(coins, amount):
    dp = [float("inf")] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if i >= c:
                dp[i] = min(dp[i], dp[i - c] + 1)
    return dp[amount] if dp[amount] != float("inf") else -1

# 回想第 16 课贪心翻车的例子：凑 8，面额 [5,4,1]
print(coin_change([5, 4, 1], 8))   # 2（用 4+4，DP 找到了最优，贪心会错）
print(coin_change([2], 3))          # -1（凑不出）

体会：第 16 课贪心在 [5,4,1] 凑 8 时翻车（给出 4 枚），而 DP 稳稳找到最优解 2 枚。这就是"贪心 vs DP"最直观的对比。

九、小结

DP = 把子问题的解记下来，避免重复计算——用空间换时间，把指数级变多项式级。
DP 两步走：先定义 dp[i] 表示什么（状态），再找 dp[i] 从谁转移来（转移方程）。
贪心赌"眼前对就全对"，DP 算"所有子问题都不错过"——贪心翻车的地方（如凑 8），DP 稳稳兜底。

先别急着往后翻，把"递归 vs DP"的时间对比跑一遍，再亲手让贪心在凑 8 上翻车、让 DP 扳回一城——这两件事都做完，你对"算法策略"的分工就彻底通了。