C++线性DP 滑雪问题

滑雪问题是一个经典的动态规划问题，可以使用线性 DP 来解决。

问题描述：给定一个二维矩阵，每个元素表示一个地点的海拔高度。从某个地点出发，只能向上、下、左、右四个方向滑雪，每次只能滑到高度小于当前位置的地点。求出从任意一个起点出发，能够滑雪的最长路径长度。

解题思路：

1. 定义一个二维数组 dp，dp[i][j] 表示以位置 (i, j) 为起点的最长路径长度。
2. 初始化 dp 数组的所有元素为 1，表示每个位置都可以自身作为起点形成长度为 1 的路径。
3. 对矩阵中的每个位置 (i, j) 进行遍历，更新 dp 数组：
   • 如果位置 (i, j) 的上方位置 (i-1, j) 的海拔高度小于当前位置，更新 dp[i][j] = max(dp[i][j], dp[i-1][j]+1)；
   • 如果位置 (i, j) 的下方位置 (i+1, j) 的海拔高度小于当前位置，更新 dp[i][j] = max(dp[i][j], dp[i+1][j]+1)；
   • 如果位置 (i, j) 的左方位置 (i, j-1) 的海拔高度小于当前位置，更新 dp[i][j] = max(dp[i][j], dp[i][j-1]+1)；
   • 如果位置 (i, j) 的右方位置 (i, j+1) 的海拔高度小于当前位置，更新 dp[i][j] = max(dp[i][j], dp[i][j+1]+1)；
4. 遍历 dp 数组，找出其中的最大值，即为所求的最长路径长度。

以下是 C++ 的实现代码：

#include <iostream>
#include <vector>
using namespace std;

int ski(vector<vector<int>>& matrix) {
    int m = matrix.size();
    int n = matrix[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 1));

    int maxLen = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i > 0 && matrix[i][j] > matrix[i-1][j]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j]+1);
            }
            if (i < m-1 && matrix[i][j] > matrix[i+1][j]) {
                dp[i][j] = max(dp[i][j], dp[i+1][j]+1);
            }
            if (j > 0 && matrix[i][j] > matrix[i][j-1]) {
                dp[i][j] = max(dp[i][j], dp[i][j-1]+1);
            }
            if (j < n-1 && matrix[i][j] > matrix[i][j+1]) {
                dp[i][j] = max(dp[i][j], dp[i][j+1]+1);
            }
            maxLen = max(maxLen, dp[i][j]);
        }
    }

    return maxLen;
}

int main() {
    vector<vector<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    int res = ski(matrix);
    cout << "The longest skiing path length is " << res << endl;

    return 0;
}

以上代码中，我们以一个 3x3 的矩阵为例进行演示，最长路径的长度为 9。你可以根据需要修改矩阵的大小和元素值进行测试