记忆化搜索(Memoization)

数据结构与算法第六章查找记忆化搜索(Memoization)

“记忆化搜索”通常指的是在动态规划或递归算法中使用的一种优化技术。通过在计算过程中将已经计算过的子问题的结果存储起来，避免重复计算，从而加快算法的执行速度。这种技术在处理涉及重叠子问题的大规模问题时特别有效。

记忆化搜索的关键步骤：

定义存储结构：通常使用一个数组或哈希表来存储已经计算过的子问题的结果。
检查存储结构：在递归调用之前，先检查这个存储结构是否已经包含了当前子问题的解。如果已经存在，则直接返回这个值。
保存计算结果：如果当前子问题的解还没有被计算过，那么计算后将其存储在存储结构中，以便后续使用。

记忆化搜索的示例（以斐波那契数列为例）：

#include <iostream>
#include <vector>

using namespace std;

vector<int> memo;

// 记忆化搜索计算斐波那契数
int fib(int n) {
    if (n <= 1) return n;
    
    // 如果已经计算过，直接返回结果
    if (memo[n] != -1) return memo[n];
    
    // 否则，计算并保存结果
    memo[n] = fib(n - 1) + fib(n - 2);
    
    return memo[n];
}

int main() {
    int n = 10;
    memo.assign(n + 1, -1);  // 初始化存储结构
    
    cout << "Fibonacci(" << n << ") = " << fib(n) << endl;
    
    return 0;
}

P1535 [USACO08MAR] Cow Travelling S