牛客233065题：最长滑雪路径的动态规划与记忆化搜索解法
8个月前 (08-27)
一、题目解读
牛客233065题要求求解给定矩阵中的最长滑雪路径。滑雪者从任意点出发，每次只能向高度严格递减的相邻格子移动（上下左右四个方向），需找到路径长度最大值。题目考察动态规划与搜索算法的结合，重点在于优化重复计算以提高效率。
二、解题思路
采用深度优先搜索（DFS）结合记忆化技术解决该问题。核心思路如下：
1. 记忆化搜索：为避免重复计算每个点的最长路径，使用二维备忘录记录已求解结果。
2. 递归式设计：从每个点出发递归搜索四周符合条件的低高度点，路径长度为其后继点最长路径+1。
3. 边界条件：严格检查矩阵边界及高度递减要求，确保路径合法性。
通过动态规划的思想，将递归搜索转化为有记忆的优化算法，显著降低时间复杂度。
三、解题步骤
1. 初始化：读取矩阵尺寸，创建与矩阵同大小的备忘录（全0表示未计算）。
2. 外层循环：遍历矩阵每个点作为起点，调用DFS函数更新最长路径结果。
3. DFS函数：
若当前点已计算，直接返回备忘录值。
遍历四个方向，对合法相邻点（边界内且高度递减）递归调用DFS，获取其最长路径。
更新当前点的路径长度为所有后继点路径最大值+1，存入备忘录。
4. 结果汇总：外层循环结束后，备忘录中存储了所有点的最长路径，取全局最大值即为答案。
四、代码与注释
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; // 四个方向
int dfs(vector<vector<int>>& matrix, vector<vector<int>>& memo, int i, int j) {
if(memo[i][j]!= 0) return memo[i][j]; // 已计算过，直接返回结果
int max_len = 1; // 至少包含自己
for(auto& dir : dirs) { // 遍历四个方向
int x = i + dir[0], y = j + dir[1];
// 边界检查且高度必须严格递减
if(x >= 0 && x < matrix.size() && y >= 0 && y < matrix[0].size()
&& matrix[x][y] < matrix[i][j]) {
max_len = max(max_len, dfs(matrix, memo, x, y) + 1);
}
}
memo[i][j] = max_len; // 记忆化存储当前点的最长路径
return max_len;
}
int longestSkiPath(vector<vector<int>>& matrix) {
if(matrix.empty()) return 0;
int n = matrix.size(), m = matrix[0].size();
vector<vector<int>> memo(n, vector<int>(m, 0)); // 初始化备忘录
int res = 0;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
res = max(res, dfs(matrix, memo, i, j)); // 更新全局最长路径
}
}
return res;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> matrix(n, vector<int>(m));
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
cin >> matrix[i][j];
}
}
cout << longestSkiPath(matrix) << endl;
return 0;
}五、总结
该解法巧妙地将动态规划思想融入DFS，通过备忘录消除递归中的重复计算，将时间复杂度优化至O(NM)（N为矩阵行数，M为列数）。代码结构清晰，边界处理严谨，是解决此类路径问题的典型范例。实际应用中，记忆化搜索常作为优化递归算法的有效手段，值得深入掌握。
原创内容 转载请注明出处
