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

class Solution {
    
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */
    int solve( const vector<vector<int> >& matrix) {
        // write code here
        vector<int> rst;
        if(matrix.size() == 0) return 0; 
        int row = matrix.size();
        int col = matrix[0].size();
        vector<vector<int> >dp(row, vector<int>(col, -1));
        int maxLen = 0;
        
        for(int i = 0; i < row; ++i)
        {
            for(int j = 0; j < col; ++j)
            {
                maxLen = max(maxLen, dfs(matrix,i, j, -1,dp));
            }
        }
        return maxLen;
        
    }
    
    int dfs(const vector<vector<int> >&matrix, int i, int j, int pre, vector<vector<int> >&dp) //&符号在大量数据传递时可以提高效率，这就是为什么加入引用符号后程序执行更快的原因
    {
        if(matrix[i][j] <= pre) return 0;
        int mx = 0;
        if(dp[i][j] != -1) return dp[i][j];
        if(i + 1 < matrix.size()) mx = max(mx, dfs(matrix, i+1, j, matrix[i][j], dp));
        if(i - 1 >= 0) mx = max(mx, dfs(matrix, i-1, j, matrix[i][j], dp));
        if(j + 1 < matrix[0].size()) mx = max(mx, dfs(matrix,i, j+1,matrix[i][j], dp));
        if(j - 1 >= 0) mx = max(mx,dfs(matrix, i, j-1, matrix[i][j],dp));
        dp[i][j] = mx+1;
        return mx+1;
    }
    
  
};