深度解析记忆化搜索：从一维到三维的优化实战指南

2026-02-03 15:01:03 0条评论 5次阅读 0人点赞

在算法学习与工程实践中，我们经常遇到一个问题：明明逻辑正确的递归代码，一旦输入规模稍大，运行时间就呈指数级增长，甚至直接超时。这通常是因为我们的算法进行了大量的重复计算。今天，我们将深入探讨一种解决此类问题的利器——记忆化搜索。这是一种结合了递归代码的高可读性与动态规划的高效率的优化技术。

通过这篇文章，你将学会如何识别重复计算，并掌握从一维到三维记忆化搜索的实现技巧。我们将通过具体的代码示例，一步步带你领略这种“自带缓存”的编程艺术。

为什么我们需要记忆化？

在大多数动态规划问题中，通常有两种标准的解决方式：

  • 制表： 即我们常说的“自底向上”，通常使用迭代来实现。
  • 记忆化： 即我们常说的“自顶向下”，通常在递归的基础上进行优化。

解决大多数 DP 问题的一个简单思路是，首先编写递归代码（因为这通常最符合问题的数学定义），然后将其改写为自底向上的制表方法，或者直接对递归函数进行自顶向下的记忆化处理。

针对任何问题，编写自顶向下 DP 解决方案的步骤如下：

  • 编写问题的递归代码。
  • 将返回值存储在某种数据结构（如哈希表或数组）中，并在下次需要该值时直接查找，从而减少递归调用。

一维记忆化：从斐波那契数列开始

让我们从最基础的一维记忆化开始。这里“一维”的意思是，在我们的递归函数中，只有一个参数的状态会发生变化。

#### 问题场景

经典的例子是斐波那契数列问题：寻找第 N 项的值。

#### 朴素的递归解法

首先，让我们看看如果不进行优化，代码是什么样的。这是最直观的数学翻译。

下面给出了寻找第 N 项的递归代码：

C++ 实现

// C++ program to find the Nth term
// of Fibonacci series
#include 
using namespace std;

// 斐波那契数列的递归实现
int fib(int n)
{
    // 基本情况：如果 n 是 0 或 1，直接返回 n
    if (n <= 1)
        return n;

    // 递归调用：前两项之和
    return fib(n - 1) + fib(n - 2);
}

// 主函数
int main()
{
    int n = 6;
    printf("%d", fib(n));
    return 0;
}

Java 实现

// Java program to find the 
// Nth term of Fibonacci series
import java.io.*;

class GFG
{    
    // 斐波那契数列的递归实现
    static int fib(int n)
    {
        // 基本情况
        if (n <= 1)
            return n;
    
        // 递归调用
        return fib(n - 1) + fib(n - 2);
    }
    
    // 主代码
    public static void main (String[] args) 
    {
        int n = 6;
        System.out.println(fib(n));
    }
}

Python3 实现

# Python3 program to find the Nth term
# of Fibonacci series

# 斐波那契数列的递归实现
def fib(n):

    # 基本情况
    if (n <= 1):
        return n

    # 递归调用
    return fib(n - 1) + fib(n - 2)

# 主代码
if __name__=='__main__':
    n = 6
    print (fib(n))

输出：

8

#### 分析性能瓶颈

让我们看看上面这段代码的性能：

  • 时间复杂度： O(2^n)

因为在每个阶段我们需要进行 2 次函数调用，且递归树的高度将是 n 的数量级。

  • 辅助空间： O(n)

由于递归调用栈而使用了额外的空间。

一个常见的观察结果是，这种实现做了很多重复的工作。让我们画出 fib(5) 的递归树来看看：

                    fib(5)   
                   /        \        
             fib(4)        fib(3)   
           /      \        /       \        
       fib(3)    fib(2)   fib(2)   fib(1)
      /   \       /    \   /      \ 
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/    \ 
fib(1) fib(0)

在上面的树中，你可以清晰地看到 INLINECODE7ed1733a, INLINECODE613585c8, INLINECODEd014c7cc, INLINECODEdb67d6a7 都被计算了不止一次。随着 N 的增加，这种重复是呈指数级爆炸的。

#### 引入记忆化搜索

为了解决这个问题，我们采用自顶向下的记忆化方法。其实质非常简单：创建一个数组（或者哈希表），充当“缓存”。

核心逻辑：

  • 在计算 fib(x) 之前，先检查缓存中是否已经有结果。
  • 如果有，直接返回。
  • 如果没有，进行计算，但在返回结果之前，先将其存入缓存。

这样，当我们再次遇到相同参数的递归调用时，就可以直接从缓存中读取，无需再次展开递归树。

优化后的 C++ 代码（一维记忆化）：

这里我们定义一个全局数组 memo 来存储值。初始化时，我们可以将其设为 -1，表示该位置尚未被计算。

// C++ program to find the Nth term
// Memoization Implementation
#include 
using namespace std;

// 定义一个全局数组用于存储计算结果
// 这里假设 N 不会超过 100
int memo[100];

// 初始化记忆化数组
void initialize() {
    memset(memo, -1, sizeof(memo));
}

// 优化的斐波那契函数
int fib(int n)
{
    // 基本情况
    if (n <= 1)
        return n;

    // 检查是否已经计算过 n 
    // 如果 memo[n] 不是 -1，说明已经存储了值
    if (memo[n] != -1)
        return memo[n];

    // 如果没有计算过，则计算并存储
    // 存储 fib(n) 的值在 memo[n] 中
    memo[n] = fib(n - 1) + fib(n - 2);

    // 返回存储的值
    return memo[n];
}

// 主代码
int main()
{
    int n = 6;
    initialize(); // 别忘了初始化
    printf("%d", fib(n));
    return 0;
}

优化分析：

  • 时间复杂度： O(N)。为什么？因为对于每一个 INLINECODE2982d729 从 0 到 INLINECODEe0c951a0，我们只计算 fib(i) 一次。之后，所有对该值的调用都是 O(1) 的查找操作。
  • 辅助空间： O(N)。这里包括递归栈的空间 O(N) 和数组存储的空间 O(N)。

二维记忆化：处理更复杂的状态

当我们遇到的问题不仅仅取决于一个变量（比如前面的 N），而是取决于两个变量（比如 INLINECODEd86d5c50 和 INLINECODEeda41d8e）时，一维数组就不够用了。这时候我们需要升级到二维记忆化。

#### 问题场景：二项式系数计算

假设我们需要计算二项式系数 $C(n, k)$，即从 n 个物品中选出 k 个的组合数。根据数学公式，$C(n, k) = C(n-1, k-1) + C(n-1, k)$。显然，这取决于 INLINECODE3d8ab6ba 和 INLINECODE158055c6 两个参数。

// C++ program for Binomial Coefficient
// using 2D Memoization
#include 
using namespace std;

// 定义二维数组用于缓存
// 大小可以根据题目限制调整
int memo[100][100];

// 初始化函数
void initialize() {
    for(int i=0; i<100; i++)
        for(int j=0; j<100; j++)
            memo[i][j] = -1;
}

// 递归函数配合记忆化
int binomialCoeff(int n, int k)
{
    // 基本情况
    if (k == 0 || k == n)
        return 1;

    // 检查缓存中是否已有 (n, k) 的值
    if (memo[n][k] != -1)
        return memo[n][k];

    // 计算并存入缓存
    memo[n][k] = binomialCoeff(n - 1, k - 1) + binomialCoeff(n - 1, k);

    return memo[n][k];
}

// 主代码
int main()
{
    int n = 5, k = 2;
    initialize();
    cout << "Value of C(" << n << ", " << k << ") is " << binomialCoeff(n, k);
    return 0;
}

关键点：

在这里，我们的状态转移依赖于 INLINECODE6ff783f2 和 INLINECODE42f79201。如果不使用记忆化，这个递归树的复杂度将达到指数级。通过使用 memo[n][k]，每个状态只会被计算一次，将时间复杂度从指数级降低到了 O(N*K)。

#### 实战应用：路径计数问题

另一个经典的二维场景是网格路径问题。想象你在一个 INLINECODE6b95c500 的网格中，你只能向右或向下移动。问从左上角 INLINECODEb8755444 到达右下角 (M-1, N-1) 有多少种不同的路径？

这个问题的递归关系是：INLINECODE258a9c71。状态由坐标 INLINECODE3a4a19f7 决定。

二维记忆化代码片段：

// 辅助函数：计算网格路径
int countPaths(int i, int j, int m, int n, vector<vector>& dp) {
    // 越界检查
    if (i >= m || j >= n) return 0;
    
    // 到达终点
    if (i == m - 1 && j == n - 1) return 1;

    // 检查缓存
    if (dp[i][j] != -1) return dp[i][j];

    // 向下走 + 向右走
    return dp[i][j] = countPaths(i + 1, j, m, n, dp) + countPaths(i, j + 1, m, n, dp);
}

三维记忆化：挑战更深层的状态空间

当我们有两个以上的变量影响递归结果时，我们需要使用三维记忆化。这在处理涉及两个交互序列的问题（如 LCS 的变体）或者带有某些额外约束的网格问题时非常常见。

#### 问题场景：带有限制的 LCS 变体

想象一个场景，我们要解决最长公共子序列（LCS）问题，但是增加了一个限制条件：比如子序列中两个相同字符之间的距离不能超过某个值，或者我们在两个字符串 INLINECODEbc5e132e 和 INLINECODEbce47cb0 上操作，同时还需要跟踪第三个状态 k（比如剩余的删除次数）。

假设我们要解决一个函数 f(i, j, k)，其中：

  • i 是字符串 A 的索引。
  • j 是字符串 B 的索引。
  • k 是当前的剩余操作次数。

三维记忆化代码结构：

处理三维记忆化时，最重要的部分是正确地初始化和访问三维数组（或 vector）。

// C++ program to demonstrate 3D Memoization
#include 
using namespace std;

// 定义三维数组：dp[i][j][k]
// 大小根据题目限制 MAX_N, MAX_M, MAX_K 设定
int dp[100][100][100];

// 初始化函数
void initialize_3d(int n, int m, int k) {
    for(int i=0; i<=n; i++)
        for(int j=0; j<=m; j++)
            for(int l=0; l<=k; l++)
                dp[i][j][l] = -1; // -1 代表未访问
}

// 示例递归函数
int solve(int i, int j, int k) {
    // 基本情况
    if (i <= 0 || j  0) {
        // 可以进行某种操作
        res = solve(i-1, j, k-1) + solve(i, j-1, k-1);
    } else {
        // 不能操作，常规逻辑
        res = solve(i-1, j, k) + solve(i, j-1, k);
    }

    // 存入缓存并返回
    return dp[i][j][k] = res;
}

注意： 三维数组非常消耗空间。在工程实践中，如果 k 的值很小，或者可以通过状态压缩（例如使用 Bitmask 或滚动数组）来优化，我们会优先考虑优化空间。但对于初学者来说，直接使用三维数组是理解状态转移最直观的方式。

实战建议与常见陷阱

在实际编码面试或项目中，仅仅“知道”记忆化是不够的，你还需要注意一些细节，以确保你的代码既高效又健壮。

#### 1. 初始化的重要性

这是最容易出错的细节。如果你使用全局数组，请务必在 INLINECODE796e45ef 函数中显式地调用 INLINECODE4fa3ac57 或循环赋值来初始化数组。如果使用 vector，可以在声明时直接赋值，例如：

vector<vector> dp(n, vector(m, -1));

如果不初始化，你的缓存中可能包含垃圾值，导致程序逻辑崩溃或答案错误。

#### 2. 全局变量 vs. 传递引用

在记忆化搜索中，我们通常将 DP 数组声明为全局变量，或者作为引用参数传递给函数。这主要是为了方便，避免在每次递归调用时都传递数组的引用或指针。在 C++ 中，全局数组在处理多维记忆化时特别常见，因为它省去了处理模板维度的麻烦。

#### 3. 何时使用记忆化 vs. 制表

  • 使用记忆化的场景：

* 递归结构非常清晰，容易写出。

* 需要计算的状态只是所有可能状态的一个子集（即“剪枝”效果明显）。例如，在某些路径搜索中，你不需要填充整个 DP 表。

* 你想快速通过算法验证逻辑，而不需要纠结循环的顺序。

  • 使用制表的场景：

* 内存非常受限。递归栈会消耗额外的内存，而迭代通常只需要常数的栈空间（或者可以优化）。

* 需要严格的性能要求。递归调用的开销有时比数组访问要大。

总结与下一步

在这篇文章中，我们从一维的斐波那契数列开始，逐步探索了二维的组合数、路径计数，以及三维的状态空间问题。我们可以看到，记忆化搜索的核心思想非常统一：

  • 写出自然的递归解。
  • 找出变化的状态（参数）。
  • 创建一个与状态维度匹配的“缓存”。
  • 在计算前查询，在计算后存储。

这种“自顶向下”的思维方式，让我们能够以更符合逻辑直觉的方式解决复杂的动态规划问题，避免了“自底向上”方法中有时会遇到的“状态循环依赖”或“循环顺序难以确定”的困扰。

接下来的步骤：

我建议你尝试解决一些经典问题来巩固这种技巧，比如：

  • 01 背包问题（二维记忆化）
  • 最长公共子序列（LCS）（二维记忆化）
  • 编辑距离（二维记忆化）

当你拿到一个问题，试着先问自己：“这个问题的递归结构是什么？有哪些参数在变化？”这通常就是你记忆化数组的维度。祝你在算法之路上玩得开心！

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。如需转载，请注明文章出处豆丁博客和来源网址。https://shluqu.cn/22501.html
点赞
0.00 平均评分 (0% 分数) - 0 票

相关文章美国1G带宽/1T流量高速vps $17.99/年