当前位置:首页 > 牛客题解 > 牛客网233065题 滑雪:记忆化搜索与动态规划的完美结合

牛客网233065题 滑雪:记忆化搜索与动态规划的完美结合

14小时前牛客题解34

截图未命名.jpg 牛客网233065题 滑雪:记忆化搜索与动态规划的完美结合 记忆化搜索 动态规划 矩阵路径 算法 牛客网题解 C++ DFS算法 递归 第1张

一、问题分析

我们需要在给定的高度矩阵中找到最长的严格递减路径(滑道),只能向上下左右四个方向移动且必须严格递减。这与经典的"矩阵最长递增路径"问题类似,但方向相反。

二、解决方案

采用‌记忆化搜索+DFS‌的方法:

  1. 遍历矩阵中的每个点作为起点

  2. 对每个点进行深度优先搜索

  3. 使用记忆化存储已计算点的最长路径

  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;
}

四、算法详解

  1. memo数组‌:存储每个点出发的最长滑道长度,避免重复计算

  2. DFS递归‌:从当前点向四个方向探索,只向更低点移动

  3. 终止条件‌:当无法继续下降时返回1(只包含自己)

五、优化与扩展

  1. 剪枝优化‌:可以先对高点排序,从高到低处理

  2. 并行计算‌:独立计算不同起点的路径

  3. 路径记录‌:修改算法可输出具体路径

这个解决方案完美结合了DFS的直观性和动态规划的高效性,是处理矩阵路径类问题的经典模式。


原创内容 转载请注明出处

分享给朋友:

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。