自顶向下的 DP 与记忆化
向递归解法中加入记忆化字典，剪枝重复调用，并使用 @lru_cache 以极少代码完成记忆化。
自顶向下的 DP 与记忆化 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
自顶向下 DP：记忆化思想
自顶向下 DP从原始递归解法开始，并添加记忆化：一种在每个子问题第一次计算时存储其结果的缓存。在之后使用相同参数的调用中，会立即返回缓存结果，而无需再次递归。这会将 O(2^n) 的朴素递归转换为 O(n)，只需对现有递归解法做极少的代码修改——通常只需添加 2～3 行。
# Top-down approach:
# 1. Write the recursive solution (natural but slow)
# 2. Add a memo dict to cache results
# 3. Before recursing, check if the result is cached
# 4. Before returning, store the result in the cache
# This is also called 'memoization' (US spelling)
# 'memoize' means 'to remember', not 'memorize'
# The cache key is the function arguments
# For fib: key is n
# For 2D DP: key is (i, j)
# For 3D DP: key is (i, j, k)
print('Top-down = recursion + memo cache')记忆化斐波那契
向朴素斐波那契递归中添加记忆字典，可将时间复杂度从 O(2^n) 降低到 O(n)。第一次调用 fib(k) 会计算并存储结果。之后对同一个 k 的所有调用都会立即返回缓存值。空间复杂度为 O(n)，其中记忆字典和调用栈各占 O(n)。比较调用次数：不使用记忆化时，fib(30) 会进行约 200 万次调用；使用记忆化时，恰好进行 30 次调用。
def fib_memo(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n] # return cached result
if n <= 1:
return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
# Verify speed improvement:
print(fib_memo(30)) # fast!
print(fib_memo(50)) # still fast
print(fib_memo(100)) # no problem
# Without memo, fib_naive(50) would take minutes
# With memo: each of the 50 sub-problems computed once使用 @functools.lru_cache
Python 的 @functools.lru_cache(maxsize=None) 装饰器（或者 Python 3.9+ 中的别名 @cache）会根据函数参数自动进行记忆化。这是在面试场景中添加自顶向下 DP 的最简洁方式——先写出递归解法，加上装饰器即可。该装饰器会将所有结果缓存到一个字典中，并以函数参数作为键；这些参数必须是可哈希的（不能使用列表——请改用元组）。
import functools
@functools.lru_cache(maxsize=None)
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
print(fib(50)) # 12586269025
print(fib(100)) # works instantly
# Clear cache between tests if needed:
fib.cache_clear()
# Python 3.9+ shorthand:
# from functools import cache
# @cache
# def fib(n): ...
print(fib.cache_info()) # shows hits, misses, maxsize, currsize自顶向下解决零钱兑换
零钱兑换（LeetCode #322）：给定硬币面额和目标金额，找出所需的最少硬币数。递归形式是：对每枚硬币，选择它，然后对剩余金额求解，最后取最小值。以金额为记忆化依据，避免重复计算。基本情况是：amount=0 需要 0 枚硬币；无法达到的金额返回无穷大（或在递归结束后返回 -1）。
import functools
def coin_change_top_down(coins, amount):
@functools.lru_cache(maxsize=None)
def dp(remaining):
if remaining == 0:
return 0 # no coins needed
if remaining < 0:
return float('inf') # impossible
# Try each coin and take the minimum
return 1 + min(dp(remaining - c) for c in coins)
result = dp(amount)
return result if result != float('inf') else -1
print(coin_change_top_down([1, 5, 6, 9], 11)) # 2: (5+6) or (2*5+1?no: 9+2?no) 5+6=11 YES
print(coin_change_top_down([2], 3)) # -1: impossible
print(coin_change_top_down([1, 2, 5], 11)) # 3: 5+5+1使用 K 步的自顶向下爬楼梯
将爬楼梯推广为允许一次走 1 到 k 步。状态是当前楼梯位置；从楼梯 i 可以到达 i+1、i+2、……、i+k 级。递推关系为：dp(i) = sum of dp(i-j) for j in 1..k if i-j >= 0。记忆化使复杂度从 O(k^n) 降为 O(n*k)。这种推广会出现在“到达最后一级的最小代价”和“统计填充网格的方案数”等问题中。
import functools
def climb_k_steps(n, k):
@functools.lru_cache(maxsize=None)
def dp(i):
if i == 0:
return 1 # base: one way to stay at ground
if i < 0:
return 0 # impossible
# From stair i, you could have come from i-1, i-2, ..., i-k
return sum(dp(i - j) for j in range(1, k+1) if i - j >= 0)
return dp(n)
# k=2 (original): should match fib-like sequence
print([climb_k_steps(n, 2) for n in range(7)]) # [1,1,2,3,5,8,13]
# k=3: more options
print([climb_k_steps(n, 3) for n in range(7)]) # [1,1,2,4,7,13,24]自顶向下 LCS：二维记忆化
最长公共子序列（LCS）需要二维状态：dp(i, j) = s1[:i] 和 s2[:j] 的 LCS 长度。如果 s1[i-1] == s2[j-1]，说明字符匹配：dp(i,j) = 1 + dp(i-1, j-1)。否则：dp(i,j) = max(dp(i-1,j), dp(i,j-1))——从任一字符串中跳过一个字符。在 (i, j) 上进行记忆化，可以将复杂度从 O(2^(m+n)) 降为 O(mn)。
import functools
def lcs_top_down(s1, s2):
m, n = len(s1), len(s2)
@functools.lru_cache(maxsize=None)
def dp(i, j):
if i == 0 or j == 0:
return 0 # empty prefix has LCS of 0
if s1[i-1] == s2[j-1]:
return 1 + dp(i-1, j-1) # characters match
return max(dp(i-1, j), dp(i, j-1)) # skip one
return dp(m, n)
print(lcs_top_down('abcde', 'ace')) # 3: 'ace'
print(lcs_top_down('abc', 'abc')) # 3: 'abc'
print(lcs_top_down('abc', 'def')) # 0: no common chars记忆字典与 lru_cache：如何选择
当函数参数是可哈希的基本类型（int、str、tuple）时，请使用 @lru_cache。在以下情况中，请使用手动记忆字典：需要传递可变状态（列表、字典），但要先将它们转换为元组；需要跟踪已经计算过的键；或者在类方法中不应缓存 self。手动记忆字典更加明确，还能避免递归辅助函数中不易察觉的闭包问题。
# @lru_cache: clean, automatic, O(1) overhead
# Use when: arguments are simple (int, str, tuple)
import functools
@functools.lru_cache(maxsize=None)
def simple_dp(n):
if n <= 1: return n
return simple_dp(n-1) + simple_dp(n-2)
# Manual memo dict: explicit, flexible
# Use when: complex state, need to inspect memo, class methods
def manual_memo_dp(s1, s2):
memo = {}
def dp(i, j):
if (i,j) in memo: return memo[(i,j)]
if i == 0 or j == 0:
return 0
if s1[i-1] == s2[j-1]:
memo[(i,j)] = 1 + dp(i-1, j-1)
else:
memo[(i,j)] = max(dp(i-1,j), dp(i,j-1))
return memo[(i,j)]
return dp(len(s1), len(s2))
print(manual_memo_dp('abcde', 'ace')) # 3自顶向下求目标和
目标和（LeetCode #494）：为每个数字分配 + 或 -，统计能得到目标和的分配方式。状态：dp(index, current_sum)。在每个索引处，尝试将当前数字相加和相减。对 (index, current_sum) 进行记忆化，可以将 O(2^n) 的暴力法转换为 O(n * sum_range)。总和范围受所有数字之和限制，因此总状态数为 O(n * S)。
import functools
def find_target_sum_ways(nums, target):
@functools.lru_cache(maxsize=None)
def dp(index, current_sum):
if index == len(nums):
return 1 if current_sum == target else 0
# Try adding the number
add = dp(index + 1, current_sum + nums[index])
# Try subtracting the number
subtract = dp(index + 1, current_sum - nums[index])
return add + subtract
return dp(0, 0)
print(find_target_sum_ways([1,1,1,1,1], 3)) # 5
print(find_target_sum_ways([1], 1)) # 1
print(find_target_sum_ways([1], -1)) # 1自顶向下与自底向上：优缺点
自顶向下（记忆化）的优点：自然易写（从递归解法开始）、只计算实际需要的子问题（惰性计算）、易于逐步添加缓存。自底向上（填表法）的优点：没有调用栈开销（不存在 Python 递归限制）、内存访问更有利于缓存、易于进行空间优化。两者具有相同的渐近复杂度。在面试中，请先从自顶向下开始以验证正确性；如果对空间有更高要求，再将其转换为自底向上。
# Top-down advantages:
# + Natural: write recursive, add @cache
# + Lazy: only computes needed sub-problems
# + Easy to reason about correctness
# - Uses call stack (recursion limit in Python)
# - Higher constant factor (function call overhead)
# Bottom-up advantages:
# + No recursion limit
# + Better cache performance (sequential memory)
# + Easier to space-optimise (rolling array)
# - Must compute all sub-problems in order
# - Less intuitive for complex 2D/3D problems
# Interview strategy:
# Start with top-down to verify recurrence,
# convert to bottom-up only if asked.
print('Top-down: easy to write | Bottom-up: efficient for large n')使用自顶向下 DP 进行单词拆分
单词拆分（LeetCode #139）要求判断字符串 s 是否可以拆分为字典中的单词。状态：dp(i) = s[i:] 是否可以拆分。从索引 i 开始，尝试所有单词：如果 s[i:i+len(w)] == w，就对剩余后缀进行递归。对起始索引进行记忆化，可以将 O(2^n) 的暴力法转换为 O(n^2)（或 O(n * max_word_len)），同时进行集合成员检查。
import functools
def word_break(s, word_dict):
word_set = set(word_dict)
@functools.lru_cache(maxsize=None)
def dp(start):
if start == len(s):
return True # successfully segmented entire string
for end in range(start + 1, len(s) + 1):
if s[start:end] in word_set and dp(end):
return True
return False
return dp(0)
print(word_break('leetcode', ['leet', 'code'])) # True
print(word_break('applepenapple', ['apple', 'pen'])) # True
print(word_break('catsandog', ['cats', 'dog', 'and', 'cat', 'san', 'andog'])) # False递归限制与迭代工具
Python 的默认递归限制是 1000（由 sys.getrecursionlimit() 设置）。对于大规模输入的 DP 问题（n = 10,000+），自顶向下记忆化会触及此限制。可选方案：使用 sys.setrecursionlimit(100000) 提高限制，或者转换为自底向上 DP。在竞赛编程中，提高限制很常见；在生产代码中，为了可靠性，请始终优先选择自底向上或迭代解法。
import sys
print('Default recursion limit:', sys.getrecursionlimit()) # 1000
# For large DP problems, increase if needed:
# sys.setrecursionlimit(100000)
# Better: convert to bottom-up DP for large n
def fib_bottom_up(n):
if n <= 1: return n
a, b = 0, 1
for _ in range(2, n+1):
a, b = b, a + b
return b
# No recursion limit issue:
print(fib_bottom_up(10000)) # works fine, no recursion快速检查
请测试您对本课程中“数据结构与算法——编程面试准备”概念的理解。
课程回顾
本课您学到了：使用记忆字典和 @lru_cache 装饰器实现自顶向下 DP，为斐波那契、零钱兑换、LCS、目标和以及单词拆分编写记忆化解法，以及何时选择自顶向下而不是自底向上。接下来我们将使用填表法和空间优化实现自底向上 DP。
常见问题解答
「自顶向下的 DP 与记忆化」课时是免费的吗？
是的 — 「自顶向下的 DP 与记忆化」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「自顶向下的 DP 与记忆化」这节课中我会学到什么？
向递归解法中加入记忆化字典，剪枝重复调用，并使用 @lru_cache 以极少代码完成记忆化。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「自顶向下的 DP 与记忆化」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 识别 DP：重叠子问题
- 自顶向下的 DP 与记忆化
- 自底向上的 DP 与制表法
- 零钱兑换与最低成本爬楼梯