贪心与动态规划初识

这是什么：贪心（每步拿眼前最优）和动态规划（把大问题拆小并记住答案），两位"策略大师"。

为什么用：递归会了，这一步该见两位"策略大师"。想问题光靠递归会慢，换一种拆法，把复杂题解得又快又稳。

如何用：本章先用超市找零看贪心怎么翻车，再回头用动态规划把它救回来。

贪心：每步都拿眼前最优

去超市付 63 元，怎么让收银员找的纸币张数最少？先找大面额，不够再找小的——这就是贪心（Greedy）：每一步都做"眼下看起来最划算"的选择。

money = 63
coins = [50, 20, 10, 5, 1]      # 面额从大到小
count = 0

for coin in coins:
    while money >= coin:        # 这个面额能找就一直找
        money -= coin
        count += 1

print(count)

你会看到：

5

63 = 50 + 10 + 1 + 1 + 1，5 张搞定。但贪心有个著名的坑——它在某些面额下会翻车：

def greedy(money, coins):
    count = 0
    for coin in coins:
        while money >= coin:
            money -= coin
            count += 1
    return count

print(greedy(30, [25, 10, 1]))

你会看到：

6

贪心选了 25 + 1 × 5 = 6 枚，可最优解是 10 × 3 = 3 枚！教训：眼前最优加起来，不一定是全局最优。人民币的面额恰好让贪心总能蒙对，换一套面额它就露馅了。

动态规划：把答案记下来

再回头看上一章的斐波那契——朴素递归慢，是因为同一个子问题被反复算了好多遍。动态规划（Dynamic Programming，简称 DP）的思路就一句话：把大问题拆成小问题，并记住小问题的答案。

Python 里加缓存只需一个装饰器 @lru_cache——它把每次的输入和结果记在小本本上，下次同样输入直接查表。数一数两种写法各要"动手"几次：

from functools import lru_cache

calls = 0

def slow_fib(n):
    global calls
    calls += 1
    if n <= 2:
        return 1
    return slow_fib(n - 1) + slow_fib(n - 2)

slow_fib(20)
print("朴素版算 fib(20)：函数被调用了", calls, "次")

calls = 0

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

fast_fib(20)
print("缓存版算 fib(20)：函数只被调用了", calls, "次")

你会看到：

朴素版算 fib(20)：函数被调用了 13529 次
缓存版算 fib(20)：函数只被调用了 20 次

调用次数差了 670 多倍，而且 n 越大差距越夸张——实测朴素版算 fib(35) 要一秒多，加了两行 @lru_cache 后瞬间出结果。这就是"记住答案"的力量：用一点记忆，换掉海量重复劳动。

逐概念解读

记忆口诀

贪心快但会翻车，动态规划记答案；重复子问题多，先查小本本再干活。

动手改

1. 把 slow_fib(20) 改成 slow_fib(25)、slow_fib(30)，看调用次数怎么涨（耐心点，别直接改到 40 😅）
2. 把找零钱的 coins 换成 [50, 20, 5, 1]（去掉 10）算 30 元，验证贪心翻车得更狠
3. 给上一章的 factorial 也加上 @lru_cache，想想：它有重复子问题吗？缓存还帮得上忙吗？

下一章：综合练习，三道经典题毕业验收 🐸