记忆化搜索-滑雪-c++递归实现

• 记忆化搜索（也称为 备忘录递归）可以理解为 深度优先搜索（DFS） 加上 数组存储已遍历值 的一种优化方法。

具体解释：

• DFS（深度优先搜索）：

  • DFS 是一种遍历算法，用于探索图或树的所有可能路径。在递归调用中，DFS 会深入到一个分支的尽头，然后回溯到上一个节点继续探索其他分支。

• 数组存储已遍历值：

  • 在通常的 DFS 中，对于每个节点或状态，可能会有很多次重复计算。例如，在求解动态规划问题时，如果没有记忆化，可能会多次计算同一个子问题。
  • 为了避免这种重复计算，记忆化搜索使用一个数组（通常称为“记忆数组”）来存储已经计算过的值。当再次遇到相同的节点或状态时，可以直接从数组中读取结果，而不是重复计算。这大大减少了计算量，提高了算法的效率。

• 记忆化搜索的关键思想：

  • 存储中间结果：每次递归计算某个状态的结果后，将结果存储在数组中。
  • 查表法：当递归调用再次遇到该状态时，首先检查数组中是否已经存储了结果，如果有，直接返回结果，而无需再次计算。

总结：

记忆化搜索就是结合了 DFS 的遍历方式和数组存储已遍历值的优化技术。通过存储已经计算过的子问题的解，可以显著减少重复计算，从而提高算法效率。

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 310;

int n, m;                // n: 行数, m: 列数
int g[N][N];             // g: 存储滑雪场高度的二维数组
int f[N][N];             // f: 记忆化数组，用于存储从每个点出发的最长路径

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; 
// dx, dy: 分别表示在四个方向上的移动（上、右、下、左）

// dp函数：计算从点(x, y)出发的最长滑行路径长度
int dp(int x, int y)
{
    int &v = f[x][y]; // v引用f[x][y]，用于减少访问f[x][y]的开销
    if (v != -1) return v;  // 如果f[x][y]已经计算过（即v不是-1），则直接返回v

    v = 1;  // 初始状态下，至少有当前点本身，路径长度为1
    for (int i = 0; i < 4; i ++ )  // 遍历四个可能的移动方向
    {
        int a = x + dx[i], b = y + dy[i];  
        // 计算新的位置(a, b)，即从(x, y)移动后的新位置
        if (a >= 1 && a <= n && b >= 1 && b <= m && g[x][y] > g[a][b])
            // 检查新位置(a, b)是否在有效范围内，并且高度小于当前点
            v = max(v, dp(a, b) + 1);  
            // 递归计算从新位置(a, b)出发的最长路径，并更新当前路径长度v
    }

    return v;  // 返回从点(x, y)出发的最长路径长度
}

int main()
{
    // 读取行数和列数
    scanf("%d%d", &n, &m);
    // 读取滑雪场的高度图
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &g[i][j]);

    memset(f, -1, sizeof f);  // 将记忆化数组f初始化为-1，表示尚未计算过

    int res = 0;  // 记录最长的滑行路径长度
    for (int i = 1; i <= n; i ++ )  
        for (int j = 1; j <= m; j ++ )
            res = max(res, dp(i, j));  // 对每个点调用dp函数，并更新最长路径长度

    printf("%d\n", res);  // 输出最长的滑行路径长度

    return 0;
}

• 代码来自yxc y总，我加了注释，方便大家阅读
• 滑雪链接戳这里