记忆化搜索
定义
记忆化搜索是一种结合了搜索和动态规划思想的方法。它通过将已经计算过的结果存储起来，在后续遇到相同情况时直接返回存储的结果，避免重复计算。
运用情况
- 当问题可以用递归方式求解，但存在大量重复计算时。
- 一些复杂的组合或搜索问题，通过记忆化来提高效率。
注意事项
- 合理设计存储结构：用于保存已经计算过的状态和结果。
- 确保正确更新和检索记忆的数据。
- 注意边界情况和特殊情况的处理，以保证记忆化的准确性。
解题思路
- 确定问题的递归结构和状态表示。
- 在递归函数中，先检查当前状态是否已经被记忆，如果是则直接返回记忆的结果。
- 如果没有记忆，则进行正常的计算，并将结果存储起来。
- 按照问题的逻辑进行递归调用和结果处理。
记忆化搜索能够有效地减少重复计算，提高算法的效率，在很多情况下是一种非常实用的技术。
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;
}代码思路
-
初始化和输入:
- 定义了常量R和C来表示二维网格的最大行数和列数。
- 使用
cin读取实际的行数r和列数c。 - 通过双重循环读取每个格子grid[i][j]的值。
-
记忆化搜索（DFS + 动态规划）:
- 定义一个dp数组，dp[i][j]表示以grid[i][j]为起点的最长递增路径长度。初始化为-1，表示尚未计算。
- 实现深度优先搜索（DFS）函数
dfs(x, y)，它计算以(x, y)为起点的最长递增路径长度。- 首先，如果当前位置的最长路径已计算过，则直接返回dp[x][y]。
- 然后，初始化当前路径长度为1（至少包含当前位置）。
- 探索四个方向（上、下、左、右），如果相邻格子的值小于当前位置的值，则递归调用dfs，并累加路径长度，取所有可能路径中的最大值。
- 最后，将计算结果存入dp[x][y]并返回。
-
计算并输出最长路径长度:
- 遍历整个网格，对每个格子调用dfs函数，更新全局变量
Length为所有起点的最长路径中的最大值。 - 输出这个最大长度。
- 遍历整个网格，对每个格子调用dfs函数，更新全局变量
总结：这段代码通过结合深度优先搜索（DFS）和动态规划（记忆化搜索）的方法，有效地解决了在一个二维网格上寻找最长递增路径的问题。记忆化搜索避免了重复计算，提高了算法效率。
改进思路
-
剪枝优化:在进行DFS时，可以在判断相邻格子是否符合条件（即值大于当前格子）之前，先检查该格子是否已经被访问过（即dp值是否已经计算过），这样可以减少不必要的递归调用，进一步优化时间复杂度。
-
使用迭代法替代递归:对于深度很大的网格，递归可能导致栈溢出。可以考虑使用栈或队列实现广度优先搜索(BFS)或迭代深度优先搜索(迭代DFS)，以减少递归调用的深度。
-
空间优化:若内存限制严格，可以考虑使用滚动数组或其它空间优化策略来减少dp数组的大小。例如，只需保留上一行或上一列的dp值，因为计算新的一行或列时只需要用到这些信息。
-
输入验证:在读取r和c时，可以加入对输入值的校验，确保它们在预设的网格大小范围内，增加程序的健壮性。
-
代码注释和可读性:增加详细的注释，尤其是对于算法的核心逻辑部分，以便于他人理解和维护。同时，对变量命名可以更加直观，如将
Length改为maxPathLength以提高代码的可读性。 -
泛化处理:如果考虑代码的通用性，可以将R和C的常量定义移至函数参数中，使得算法能灵活适应不同大小的网格，提高代码的复用性。
-
并行计算:对于大规模的网格，可以探索并行计算的可能性，比如使用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。 - 最后输出最长长度。
