Coding Interview Prep · 课时

记忆化：缓存递归结果

Q: 「记忆化：缓存递归结果」这节课中我会学到什么？

对斐波那契和爬楼梯问题应用 @functools.lru_cache 与手动记忆化字典，消除指数级重复计算。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

对斐波那契和爬楼梯问题应用 @functools.lru_cache 与手动记忆化字典，消除指数级重复计算。

记忆化：缓存递归结果 是 CoddyKit 上的免费 Coding Interview Prep 课时。这是第 4 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。

冗余递归的问题

朴素递归斐波那契数列会重复计算相同的值。fib(5) 会调用 fib(4) 和 fib(3)；fib(4) 会调用 fib(3) 和 fib(2)——因此 fib(3) 会被计算两次。这种冗余会呈指数级增长：fib(40) 会产生超过十亿次函数调用。记忆化通过在每个结果第一次计算出来时将其存储起来解决了这一问题，因此后续调用可以在 O(1) 内取出结果，而不必重新计算。

# Count calls without memoisation
call_count = [0]

def fib_plain(n):
    call_count[0] += 1
    if n <= 1: return n
    return fib_plain(n-1) + fib_plain(n-2)

fib_plain(20)
print(f'fib(20) without memo: {call_count[0]:,} calls')
# ~21,891 calls for n=20; ~1 billion for n=40

使用字典进行手动记忆化

将 memo 字典作为参数传入（或使用闭包）。计算之前，检查答案是否已经存在于 memo 中。如果存在，立即返回。如果不存在，则计算答案，将其存入 memo，然后返回。现在，每个不同的子问题只会被计算一次，使 time 复杂度从 O(2^n) 降为 O(n)，空间复杂度为 O(n)（用于 memo 字典）加上 O(n) 的栈空间。

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

print(fib_memo(10))   # 55
print(fib_memo(50))   # 12586269025
print(fib_memo(100))  # huge number — still fast!

functools.lru_cache 装饰器

Python 提供了 @functools.lru_cache(maxsize=None)（Python 3.9 及更高版本中也可以使用 @functools.cache）来自动完成记忆化。在函数上方添加这个装饰器后，所有调用都会按照参数进行缓存。maxsize=None 表示缓存大小不受限制——每种不同的参数组合都会被缓存。这样，只需一行代码，就能将任意递归函数转换为记忆化版本。

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))  # 354224848179261915075
print(fib.cache_info())  # CacheInfo(hits=..., misses=..., maxsize=None, currsize=...)

爬楼梯（LeetCode 70）

LeetCode 70“爬楼梯”：您一次可以爬 1 级或 2 级台阶。到达第 n 级台阶有多少种方法？这实际上是斐波那契数列：ways(n) = ways(n-1) + ways(n-2)。基本情况是：ways(0) = 1（留在地面上也算一种方法）和 ways(1) = 1。使用记忆化后，time 复杂度为 O(n)，空间复杂度为 O(n)。

import functools

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

for i in range(1, 8):
    print(f'climbStairs({i}) = {climbStairs(i)}')
# 1,2,3,5,8,13,21

零钱兑换（LeetCode 322）

LeetCode 322“零钱兑换”：给定各种面额和一个目标金额，请找出凑出该金额所需的最少硬币数量。自顶向下的记忆化递归为：对于每个有效硬币，使用 dp(amount) = 1 + min(dp(amount - coin))。基本情况是：dp(0) = 0。缓存每个子金额。如果某个子金额无法凑出，则返回无穷大。记忆化会将指数级的暴力搜索转换为 time 复杂度 O(amount × len(coins))。

import functools

def coinChange(coins, amount):
    @functools.lru_cache(maxsize=None)
    def dp(rem):
        if rem == 0:
            return 0
        if rem < 0:
            return float('inf')
        return 1 + min(dp(rem - c) for c in coins)

    result = dp(amount)
    return result if result != float('inf') else -1

print(coinChange([1, 5, 11], 15))  # 3 (5+5+5)
print(coinChange([1, 2, 5], 11))   # 3 (5+5+1)
print(coinChange([2], 3))          # -1

使用记忆化的单词拆分（LeetCode 139）

LeetCode 139“单词拆分”：判断一个字符串是否可以拆分为字典中的单词。自顶向下的递归会尝试每个前缀 s[start:end]，如果该前缀存在于字典中且 can_break(s, end) 为真，则返回真。不使用记忆化时，复杂度为 O(2^n)；使用记忆化（缓存每个起始索引）后，复杂度变为 O(n² × L)，其中 L 是单词的最大长度。

import functools

def wordBreak(s, wordDict):
    word_set = set(wordDict)

    @functools.lru_cache(maxsize=None)
    def can_break(start):
        if start == len(s):
            return True
        for end in range(start + 1, len(s) + 1):
            if s[start:end] in word_set and can_break(end):
                return True
        return False

    return can_break(0)

print(wordBreak('leetcode', ['leet', 'code']))    # True
print(wordBreak('applepenapple', ['apple','pen'])) # True
print(wordBreak('catsandog', ['cats','dog','sand','and','cat']))  # False

记忆化与制表法

记忆化（自顶向下）从原始问题开始，在递归过程中发现答案时将其缓存起来。它只解决实际需要的子问题。制表法（自底向上）从较小的子问题到较大的子问题预先填充表格，无论是否需要都会解决所有子问题。记忆化更容易从递归解法推导出来；制表法则避免了递归深度限制和函数调用开销。

# Memoisation (top-down)
import functools
@functools.lru_cache(maxsize=None)
def fib_td(n):
    if n <= 1: return n
    return fib_td(n-1) + fib_td(n-2)

# Tabulation (bottom-up)
def fib_bu(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]

print(fib_td(20), fib_bu(20))   # 6765 6765
# Both O(n) time; fib_bu avoids recursion limit

空间优化：滚动变量

许多通过记忆化递归以 O(n) 空间解决的 DP 问题，在只需要固定数量的前置子问题答案时，还可以进一步优化到 O(1) 空间。对于斐波那契数列，只需要最后两个值；爬楼梯问题也是如此。使用两个滚动变量即可替代整个 memo 字典或表格。

# Fibonacci with O(1) space
def fib_o1(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev2 + prev1
    return prev1

for i in range(8):
    print(f'fib({i})={fib_o1(i)}', end='  ')
print()

# Climbing stairs O(1) space
def climbStairs_o1(n):
    if n <= 1: return 1
    a, b = 1, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b
print(climbStairs_o1(10))  # 89

lru_cache、闭包与全局字典

手动实现记忆化有三种方式。全局字典很简单，但会污染模块作用域。闭包将缓存封装在函数内部，可以防止泄漏，但需要额外的包装器。@lru_cache 最简洁——一个装饰器就能替代所有样板代码。在面试场景中，除非面试官明确要求手动实现，否则请从 @lru_cache 开始。

import functools

# 1. Global dict (messy)
memo_global = {}
def fib_global(n):
    if n in memo_global: return memo_global[n]
    if n <= 1: return n
    memo_global[n] = fib_global(n-1) + fib_global(n-2)
    return memo_global[n]

# 2. Closure (cleaner scope)
def make_fib():
    cache = {}
    def fib(n):
        if n in cache: return cache[n]
        if n <= 1: return n
        cache[n] = fib(n-1) + fib(n-2)
        return cache[n]
    return fib
fib_closure = make_fib()

# 3. lru_cache (best)
@functools.lru_cache(maxsize=None)
def fib_cached(n):
    if n <= 1: return n
    return fib_cached(n-1) + fib_cached(n-2)

print(fib_global(30), fib_closure(30), fib_cached(30))  # all 832040

记忆化无效的情况

记忆化只会加速具有重叠子问题的问题——也就是同一个子问题会被计算多次的情况。如果每个子问题都是唯一的（例如简单的树遍历，其中每个节点只访问一次），记忆化只会增加开销而没有任何收益。此外，如果递归树的指数增长是相对于不同子问题的数量而言，而不是由于重复使用造成的，记忆化也无法解决这类问题——这需要完全不同的算法。

# Memoisation DOES help: overlapping sub-problems (Fibonacci)
# fib(n) reuses fib(n-2), fib(n-3), etc.

# Memoisation does NOT help: distinct sub-problems (permutations)
# Each unique (remaining_elements, target) pair is truly distinct
# The exponential complexity comes from the state space itself

print('Memoisation: useful when SAME sub-problem recurs multiple times')
print('Not useful: when every sub-problem is unique to one recursive path')

总结：记忆化检查清单

在以下情况下应用记忆化：您有一个正确但由于重复计算而运行缓慢的递归解法；函数具有较少的不同参数组合；并且返回值只取决于参数（纯函数——没有副作用，也没有全局状态）。请检查子问题的状态空间：如果不同状态最多为 O(n) 或 O(n²)，记忆化就能将指数级 time 复杂度转换为多项式 time 复杂度。

快速检查

请检验您对本课中“数据结构与算法——编程面试准备”概念的理解。

课程回顾

在本课中，您学到了：记忆化会存储子问题的结果以避免重复计算，将指数级递归转换为多项式 time 复杂度；@functools.lru_cache 是符合 Python 惯用方式的工具，只需一行代码；以及记忆化（自顶向下）和制表法（自底向上）是 DP 的两种形式——记忆化更容易推导，制表法可以避免栈深度问题。恭喜您——您已经完成了递归和哈希映射模块！

常见问题解答

「记忆化：缓存递归结果」课时是免费的吗？

是的 — 「记忆化：缓存递归结果」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。

「记忆化：缓存递归结果」这节课中我会学到什么？

对斐波那契和爬楼梯问题应用 @functools.lru_cache 与手动记忆化字典，消除指数级重复计算。你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Coding Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 4 节课，共 4 节。

「记忆化：缓存递归结果」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Coding Interview Prep 课中编写并运行代码吗？

能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 Coding Interview Prep