矩阵动态规划-最长递减路径

洛谷：P1434
OJ平台：T1280

Michael 喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：

1   2   3   4   5
16  17  18  19  6
15  24  25  20  7
14  23  22  21  8
13  12  11  10  9

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度会减小。在上面的例子中，一条可行的滑坡为 24−17−16−124−17−16−1（从 2424 开始，在 11 结束）。当然 2525－2424－2323－……－33－22－11 更长。事实上，这是最长的一条。

输入格式

输入的第一行为表示区域的二维数组的行数 RR 和列数 CC。下面是 RR 行，每行有 CC 个数，代表高度(两个数字之间用 11 个空格间隔)。

输出格式

输出区域中最长滑坡的长度。

这个问题是一个典型的 动态规划（Dynamic Programming）+ 记忆化搜索（Memoization Search） 的问题。我们需要在给定的矩阵上找到一个 严格递减 的最长路径。

问题分析

输入： 一个 R×CR \times CR×C 的矩阵，矩阵元素的值范围是 0∼1000 \sim 1000∼100。
目标： 找到从任意起点出发的严格递减的最长路径，路径可以沿着上下左右四个方向移动，但不能越界。
方法：
- 记忆化搜索： 对每个格子，计算从该格子出发的最长路径长度，并将结果存储以避免重复计算。
- 动态规划递推： 从结果中找到全局最长路径。

算法步骤

定义方向数组： 用于表示上下左右四个方向的移动。
记忆数组： 定义一个 dp[i][j]数组，表示从位置 (i,j) 出发的最长严格递减路径长度。
状态转移： 如果 matrix[x][y]>matrix[nx][ny]，从位置(x,y) 可以移动到位置 (nx, ny)(nx,ny)，则 dp[x][y]=max⁡(dp[x][y],1+dp[nx][ny])
初始化和求解： 遍历每个格子，调用递归函数计算每个起点的最长路径，最终取最大值。

代码实现：

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-01-03 20:12:14
 * 最后修改: 2025-01-03 21:47:18
 * 文件描述: 在矩阵中最长递减路径
****************************************************************/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 定义上下左右四个方向
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

int R, C;
vector<vector<int>> matrix; // 输入的矩阵
vector<vector<int>> dp;     // 记忆化数组

// 记忆化搜索函数
int dfs(int x, int y) {
    // 如果已经计算过 dp[x][y]，直接返回                                                                                                                                                                                                                                                                                       
    if (dp[x][y] != -1) return dp[x][y];
    
    dp[x][y] = 1; // 初始化路径长度为1（起点自身）
    
    // 尝试向四个方向移动
    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        // 判断是否越界以及是否满足严格递减
        if (nx >= 0 && nx < R && ny >= 0 && ny < C && matrix[x][y] > matrix[nx][ny]) {
            dp[x][y] = max(dp[x][y], 1 + dfs(nx, ny));
        }
    }
    return dp[x][y];
}

int main() {
    cin >> R >> C;
    matrix.assign(R, vector<int>(C)); 
    dp.assign(R, vector<int>(C, -1));
    
    // 输入矩阵
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            cin >> matrix[i][j];
        }
    }
    
    int max_length = 0; // 记录全局最长路径长度
    
    // 遍历每个格子作为起点，计算最长路径
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            max_length = max(max_length, dfs(i, j));
        }
    }
    
    cout << max_length << endl; // 输出最长路径长度
    return 0;
}

Previous Topic

Back to Lesson

Next Topic

数据结构与算法

矩阵动态规划-最长递减路径

输入格式

输出格式

问题分析

算法步骤