备忘录法

介绍

备忘录法（Memoization）是动态规划中的一种优化技术，用于解决递归算法中的重复计算问题。它的核心思想是：在递归过程中，将已经计算过的子问题的结果存储起来，当再次遇到相同的子问题时，直接返回存储的结果，而不是重新计算。这种方法可以显著减少计算量，提高算法的效率。

备注

备忘录法通常用于解决具有重叠子问题和最优子结构性质的问题，例如斐波那契数列、背包问题等。

为什么需要备忘录法？

在递归算法中，许多子问题会被重复计算多次。例如，计算斐波那契数列时，fib(n) 会重复计算 fib(n-1) 和 fib(n-2)，而这些子问题又会进一步分解为更小的子问题。这种重复计算会导致算法的时间复杂度呈指数级增长。

通过备忘录法，我们可以将每个子问题的解存储起来，从而避免重复计算，将时间复杂度从指数级降低到线性级。

备忘录法的实现

备忘录法的实现通常包括以下步骤：

定义存储结构：使用数组、哈希表等数据结构来存储子问题的解。
检查存储：在计算子问题之前，先检查是否已经存储了该子问题的解。
存储结果：如果子问题的解尚未存储，则计算并存储结果。
返回结果：返回存储的结果。

代码示例：斐波那契数列

以下是一个使用备忘录法计算斐波那契数列的示例：

python
def fib(n, memo={}):
    # 检查是否已经计算过该子问题
    if n in memo:
        return memo[n]
    
    # 基本情况
    if n <= 1:
        return n
    
    # 递归计算并存储结果
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

# 示例输入
n = 10
# 示例输出
print(fib(n))  # 输出：55

在这个示例中，我们使用了一个字典 memo 来存储已经计算过的斐波那契数列的值。每次递归调用时，首先检查 memo 中是否已经存在该值，如果存在则直接返回，否则进行计算并存储结果。

实际应用场景

备忘录法在许多实际问题中都有广泛应用，以下是一些常见的应用场景：

1. 斐波那契数列

如上所述，斐波那契数列是备忘录法的经典应用场景。通过备忘录法，我们可以将时间复杂度从 O(2^n) 降低到 O(n)。

2. 背包问题

在背包问题中，我们需要选择一些物品放入背包，使得总价值最大。备忘录法可以帮助我们避免重复计算子问题的解，从而提高算法的效率。

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

在计算两个字符串的最长公共子序列时，备忘录法可以存储已经计算过的子问题的解，从而避免重复计算。

总结

备忘录法是一种强大的优化技术，特别适用于具有重叠子问题和最优子结构性质的问题。通过存储子问题的解，备忘录法可以显著减少计算量，提高算法的效率。

提示

在实际应用中，备忘录法通常与递归结合使用，但也可以与迭代结合使用，具体取决于问题的性质。

附加资源与练习

练习：尝试使用备忘录法解决以下问题：
- 计算第 n 个卡特兰数（Catalan Number）。
- 解决 0-1 背包问题。
进一步学习：
- 了解动态规划中的另一种优化技术——自底向上法（Bottom-Up Approach）。
- 探索更多动态规划问题，如矩阵链乘法、最短路径问题等。

介绍​

为什么需要备忘录法？​

备忘录法的实现​

代码示例：斐波那契数列​

实际应用场景​

1. 斐波那契数列​

2. 背包问题​

3. 最长公共子序列（LCS）​

总结​

附加资源与练习​

介绍