题解 | #矩阵最长递增路径# 我觉得还是对dfs应该再系统看一下。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */
    
        int solve(vector<vector<int> >& matrix) {
        int len = matrix.size();
        if (len == 0 || matrix[0].size() == 0) {
            return 0;
        }
        vector<vector<int>>dp(len, vector<int>(matrix[0].size(), 0));
            
        int ret = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < matrix[0].size(); j++) {
                int temp = dfs(matrix, dp, i, j, -1);
                ret = max(ret, temp);
            }
        }
        return ret;
    }
    int dfs(vector<vector<int> >& matrix, vector<vector<int> >& dp, int x, int y, int pre) {
        // 对x，y的范围定界
        if (x < 0 || x >= matrix.size() || y < 0 || y >= matrix[0].size()) {
            return 0;
        }
        // 如果下一个值小于当前值，直接return
        if(matrix[x][y] <= pre) {
            return 0;
        }
        // 保证不再重复遍历
        if(dp[x][y] != 0) { 
            return dp[x][y]; 
        }
        
        int tempMax = 0;
        int left = dfs(matrix, dp, x - 1, y, matrix[x][y]);
        tempMax = left;
        int right = dfs(matrix, dp, x + 1, y, matrix[x][y]);
        tempMax = max(right, tempMax);
        int up = dfs(matrix, dp, x, y + 1, matrix[x][y]);
        tempMax = max(up, tempMax);
        int down = dfs(matrix, dp, x, y - 1, matrix[x][y]);
        tempMax = max(down, tempMax);
        
        dp[x][y] = tempMax + 1; // + 1是因为也包括当前的
        return dp[x][y];
    }

};