记忆化搜索

记忆化搜索是一种通过存储已经计算过的结果来优化搜索过程的技术。
它结合了动态规划的效率和深度优先搜索的简洁性，特别适合解决具有重叠子问题的搜索问题。

基本概念

记忆化搜索的核心思想是：

在搜索过程中记录已经计算过的状态
当再次遇到相同状态时直接返回记录的结果
避免重复计算，提高效率
本质是"自顶向下"的动态规划

实现方式

记忆化搜索主要包含以下步骤：

设计状态表示方式
创建记忆化数组/哈希表
实现递归搜索函数
在搜索前检查是否已有记录
在返回前保存结果

基本实现

cpp
java
python

int fibonacci(int n, vector<int>& memo) {
    // 基础情况
    if (n <= 1) return n;
    
    // 检查是否已经计算过
    if (memo[n] != -1) return memo[n];
    
    // 计算并存储结果
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo);
    return memo[n];
}

int fib(int n) {
    vector<int> memo(n + 1, -1);
    return fibonacci(n, memo);
}

public class Solution {
    public int fibonacci(int n, int[] memo) {
        // 基础情况
        if (n <= 1) return n;
        
        // 检查是否已经计算过
        if (memo[n] != -1) return memo[n];
        
        // 计算并存储结果
        memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo);
        return memo[n];
    }
    
    public int fib(int n) {
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return fibonacci(n, memo);
    }
}

def fibonacci(n, memo=None):
    if memo is None:
        memo = {}
    
    # 基础情况
    if n <= 1:
        return n
    
    # 检查是否已经计算过
    if n in memo:
        return memo[n]
    
    # 计算并存储结果
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

应用场景

记忆化搜索在很多问题中都有应用：

动态规划问题
路径搜索问题
状态转移问题
博弈问题
组合优化问题

示例：最长公共子序列

cpp
java
python

int lcs(string& s1, string& s2, int i, int j, vector<vector<int>>& memo) {
    // 基础情况
    if (i == 0 || j == 0) return 0;
    
    // 检查记忆化数组
    if (memo[i][j] != -1) return memo[i][j];
    
    // 计算结果
    if (s1[i-1] == s2[j-1]) {
        memo[i][j] = 1 + lcs(s1, s2, i-1, j-1, memo);
    } else {
        memo[i][j] = max(lcs(s1, s2, i-1, j, memo), 
                         lcs(s1, s2, i, j-1, memo));
    }
    
    return memo[i][j];
}

int longestCommonSubsequence(string s1, string s2) {
    vector<vector<int>> memo(s1.length() + 1, 
                            vector<int>(s2.length() + 1, -1));
    return lcs(s1, s2, s1.length(), s2.length(), memo);
}

public class Solution {
    public int lcs(String s1, String s2, int i, int j, Integer[][] memo) {
        // 基础情况
        if (i == 0 || j == 0) return 0;
        
        // 检查记忆化数组
        if (memo[i][j] != null) return memo[i][j];
        
        // 计算结果
        if (s1.charAt(i-1) == s2.charAt(j-1)) {
            memo[i][j] = 1 + lcs(s1, s2, i-1, j-1, memo);
        } else {
            memo[i][j] = Math.max(lcs(s1, s2, i-1, j, memo),
                                 lcs(s1, s2, i, j-1, memo));
        }
        
        return memo[i][j];
    }
    
    public int longestCommonSubsequence(String s1, String s2) {
        Integer[][] memo = new Integer[s1.length() + 1][s2.length() + 1];
        return lcs(s1, s2, s1.length(), s2.length(), memo);
    }
}

def lcs(s1, s2, i, j, memo=None):
    if memo is None:
        memo = {}
    
    # 基础情况
    if i == 0 or j == 0:
        return 0
    
    # 检查记忆化字典
    if (i, j) in memo:
        return memo[(i, j)]
    
    # 计算结果
    if s1[i-1] == s2[j-1]:
        memo[(i, j)] = 1 + lcs(s1, s2, i-1, j-1, memo)
    else:
        memo[(i, j)] = max(lcs(s1, s2, i-1, j, memo),
                          lcs(s1, s2, i, j-1, memo))
    
    return memo[(i, j)]

def longest_common_subsequence(s1, s2):
    return lcs(s1, s2, len(s1), len(s2))

时间复杂度

未优化的递归： $\mathcal{O}(2^n)$ （以斐波那契数列为例）
记忆化搜索： $\mathcal{O}(n)$ （每个状态只计算一次）

空间复杂度

$\mathcal{O}(n)$ 或 $\mathcal{O}(n^2)$ ，取决于问题的状态数量
需要额外的空间来存储记忆化数组/哈希表

记忆化搜索 vs 动态规划

记忆化搜索是"自顶向下"，动态规划是"自底向上"
记忆化搜索实现更直观，代码更简洁
记忆化搜索有递归调用开销，动态规划效率可能更高
记忆化搜索可以按需计算，动态规划需要计算所有状态

注意事项

设计合适的状态表示
注意递归深度限制
选择合适的记忆化容器（数组/哈希表）
考虑空间复杂度和缓存命中率

练习建议

从简单的递归问题开始（如斐波那契数列）
尝试经典动态规划问题的记忆化解法
比较记忆化搜索和动态规划的异同
练习不同状态表示方式的设计

经典例题

滑雪

01.03_记忆化搜索

记忆化搜索

基本概念

实现方式

基本实现

应用场景

示例：最长公共子序列

时间复杂度

空间复杂度

记忆化搜索 vs 动态规划

注意事项

练习建议

经典例题

全站热榜

创作者周榜