记忆化搜索——AcWing 901. 滑雪_忆化搜索】901. 滑雪

记忆化搜索

定义

记忆化搜索是一种结合了搜索和动态规划思想的方法。它通过将已经计算过的结果存储起来，在后续遇到相同情况时直接返回存储的结果，避免重复计算。

运用情况

• 当问题可以用递归方式求解，但存在大量重复计算时。
• 一些复杂的组合或搜索问题，通过记忆化来提高效率。

注意事项

• 合理设计存储结构：用于保存已经计算过的状态和结果。
• 确保正确更新和检索记忆的数据。
• 注意边界情况和特殊情况的处理，以保证记忆化的准确性。

解题思路

• 确定问题的递归结构和状态表示。
• 在递归函数中，先检查当前状态是否已经被记忆，如果是则直接返回记忆的结果。
• 如果没有记忆，则进行正常的计算，并将结果存储起来。
• 按照问题的逻辑进行递归调用和结果处理。

记忆化搜索能够有效地减少重复计算，提高算法的效率，在很多情况下是一种非常实用的技术。

AcWing 901. 滑雪   

题目描述

901. 滑雪 - AcWing题库

运行代码

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int R = 300;
const int C = 300;
int r, c;
int grid[R][C];
int dp[R][C];
int dfs(int x, int y) {
    if (dp[x][y]!= -1) {
        return dp[x][y];
    }
    int maxLen = 1;
    if (x > 0 && grid[x - 1][y] < grid[x][y]) {
        maxLen = max(maxLen, 1 + dfs(x - 1, y));
    }
    if (x < r - 1 && grid[x + 1][y] < grid[x][y]) {
        maxLen = max(maxLen, 1 + dfs(x + 1, y));
    }
    if (y > 0 && grid[x][y - 1] < grid[x][y]) {
        maxLen = max(maxLen, 1 + dfs(x, y - 1));
    }
    if (y < c - 1 && grid[x][y + 1] < grid[x][y]) {
        maxLen = max(maxLen, 1 + dfs(x, y + 1));
    }
    dp[x][y] = maxLen;
    return maxLen;
}
int main() {
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> grid[i][j];
        }
    }
    memset(dp, -1, sizeof(dp));
    int Length = 0;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            Length = max(Length, dfs(i, j));
        }
    }
    cout << Length << endl;
    return 0;
}

代码思路

1. 初始化和输入:

   • 定义了常量R和C来表示二维网格的最大行数和列数。
   • 使用cin读取实际的行数r和列数c。
   • 通过双重循环读取每个格子grid[i][j]的值。

2. 记忆化搜索（DFS + 动态规划）:

   • 定义一个dp数组，dp[i][j]表示以grid[i][j]为起点的最长递增路径长度。初始化为-1，表示尚未计算。
   • 实现深度优先搜索（DFS）函数dfs(x, y)，它计算以(x, y)为起点的最长递增路径长度。
     • 首先，如果当前位置的最长路径已计算过，则直接返回dp[x][y]。
     • 然后，初始化当前路径长度为1（至少包含当前位置）。
     • 探索四个方向（上、下、左、右），如果相邻格子的值小于当前位置的值，则递归调用dfs，并累加路径长度，取所有可能路径中的最大值。
     • 最后，将计算结果存入dp[x][y]并返回。

3. 计算并输出最长路径长度:

   • 遍历整个网格，对每个格子调用dfs函数，更新全局变量Length为所有起点的最长路径中的最大值。
   • 输出这个最大长度。

总结：这段代码通过结合深度优先搜索（DFS）和动态规划（记忆化搜索）的方法，有效地解决了在一个二维网格上寻找最长递增路径的问题。记忆化搜索避免了重复计算，提高了算法效率。

改进思路

1. 剪枝优化:在进行DFS时，可以在判断相邻格子是否符合条件（即值大于当前格子）之前，先检查该格子是否已经被访问过（即dp值是否已经计算过），这样可以减少不必要的递归调用，进一步优化时间复杂度。

2. 使用迭代法替代递归:对于深度很大的网格，递归可能导致栈溢出。可以考虑使用栈或队列实现广度优先搜索(BFS)或迭代深度优先搜索(迭代DFS)，以减少递归调用的深度。

3. 空间优化:若内存限制严格，可以考虑使用滚动数组或其它空间优化策略来减少dp数组的大小。例如，只需保留上一行或上一列的dp值，因为计算新的一行或列时只需要用到这些信息。

4. 输入验证:在读取r和c时，可以加入对输入值的校验，确保它们在预设的网格大小范围内，增加程序的健壮性。

5. 代码注释和可读性:增加详细的注释，尤其是对于算法的核心逻辑部分，以便于他人理解和维护。同时，对变量命名可以更加直观，如将Length改为maxPathLength以提高代码的可读性。

6. 泛化处理:如果考虑代码的通用性，可以将R和C的常量定义移至函数参数中，使得算法能灵活适应不同大小的网格，提高代码的复用性。

7. 并行计算:对于大规模的网格，可以探索并行计算的可能性，比如使用OpenMP或其他并行计算框架来加速计算各个起始点的最长路径长度。

改进代码（AI）

#include <iostream>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;
 
const int R = 300;
const int C = 300;
int r, c;
int grid[R][C];
int dp[R][C];
int dx[] = {-1, 1, 0, 0}; // 方向数组，分别对应上、下、左、右
int dy[] = {0, 0, -1, 1};
 
int dfsIterative(int x, int y) {
    stack<pair<int, int>> stk; // 使用栈模拟深度优先搜索
    stk.push({x, y});
    int maxLength = 1;
    dp[x][y] = 1; // 初始化已访问的格子长度为1
 
    while (!stk.empty()) {
        auto [curX, curY] = stk.top(); stk.pop();
        for (int dir = 0; dir < 4; ++dir) {
            int newX = curX + dx[dir];
            int newY = curY + dy[dir];
            if (newX >= 0 && newX < r && newY >= 0 && newY < c && 
                grid[newX][newY] > grid[curX][curY] && (dp[newX][newY] == -1 || dp[newX][newY] < dp[curX][curY] + 1)) {
                dp[newX][newY] = dp[curX][curY] + 1;
                maxLength = max(maxLength, dp[newX][newY]);
                stk.push({newX, newY});
            }
        }
    }
    return maxLength;
}
 
int main() {
    cin >> r >> c;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            cin >> grid[i][j];
        }
    }
    memset(dp, -1, sizeof(dp)); // 初始化dp数组为-1
    int maxPathLength = 0;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            if (dp[i][j] == -1) { // 避免重复计算
                maxPathLength = max(maxPathLength, dfsIterative(i, j));
            }
        }
    }
    cout << maxPathLength << endl;
    return 0;
}

其它代码

#include <iostream>
#include <cstring> 
using namespace std;
const int N = 310;
int n, m;
int h[N][N];
int f[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dfs(int x, int y)
{
    int &v = f[x][y];
    if(~v) return v;
    v = 1;
    for(int i = 0; i < 4; i++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(a >= 1 && a <= n && b >= 1 && b <= m && h[a][b] < h[x][y])
             v = max(v, dfs(a, b) + 1);
    }
    return v;
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int  j = 1; j <= m; j++)
            cin >> h[i][j];
    int res = 0;
    memset(f, -1, sizeof f);
    for(int i = 1; i <= n; i++)
        for(int  j = 1; j <= m; j++)
            res = max(res, dfs(i, j));
    cout <<res <<endl;
    return 0;
}

代码思路

• 定义了一些常量和变量：
  • N 表示最大的行列数。
  • n 和 m 表示实际的行数和列数。
  • h[N][N] 存储矩阵中每个位置的高度值。
  • f[N][N] 用于记忆化已经计算过的最长滑雪长度。
• dx 和 dy 数组定义了四个方向的移动偏移量。
• dfs 函数是核心的搜索函数：
  • 通过引用获取 f[x][y]，如果已经计算过（不为 -1），则直接返回。
  • 初始化当前位置的最长长度为 1。
  • 遍历四个方向，检查新位置是否合法且高度小于当前位置，如果是，则递归调用 dfs 并更新当前位置的最长长度为递归结果加 1 的最大值。
• 在 main 函数中：
  • 输入矩阵的行数和列数以及每个位置的高度。
  • 初始化 f 数组为 -1。
  • 通过两层循环对每个位置调用 dfs 函数，获取最长长度，并不断更新结果 res。
  • 最后输出最长长度。