题解 | #矩阵最长递增路径#

class Solution {
    vector<int> direction = {-1, 0, 1, 0, -1};
    int dfs(vector<vector<int>>& matrix, int x, int y, vector<vector<int>>& dp){
	  // 如果不为零，说明在之前的递归中已经计算过以（x, y）为起点的最长路径，此时直接返回即可
        if(dp[x][y]!=0) return dp[x][y];
	  // 1. 如果为零，首先赋值自身为1
        dp[x][y] = 1;
	  // 2. 分别从四个方向出发计算最长路径长度
        for(int k=0; k<4; ++k){
            int xx = x + direction[k];
            int yy = y + direction[k+1];
		  // 3. 先判断是否越界，再判断大小是否满足递增
            if(xx>=0 && xx<matrix.size() && yy>=0 && yy<matrix[0].size() && matrix[xx][yy]>matrix[x][y]){
			  // 4. 取不同搜索方向中的最长路径
                dp[x][y] = max(dp[x][y], 1+dfs(matrix, xx, yy, dp));
            }
        }
        return dp[x][y];
    }
public:
    /**
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */
    int solve(vector<vector<int> >& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        // dp[i][j]代表以matrix[i][j]为起点的最长递增路径长度
        vector<vector<int>> dp(m, vector<int>(n));
        int res = 0;
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
			  // 以不同坐标元素为起点计算最长路径长度，取最大者
                res = max(res, dfs(matrix, i, j, dp));
            }
        }
        return res;
    }
};