当前位置：首页 > 牛客 > 牛客233065题：最长滑雪路径的动态规划与记忆化搜索解法

牛客233065题：最长滑雪路径的动态规划与记忆化搜索解法

6个月前 (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;
}