Sharing my C++ soln; 76ms; beats 89.95%;


  • 1
    H

    Just a normal recursion embedded in a memoization

    class Solution {
    public:
        int m,n;
        bool isOk(int x, int y){
            return x>=0 && x<m && y>=0 && y<n;
        }
        int dfs(vector<vector<int>>& matrix, int x, int y, vector<vector<int>> &dp){
            if(isOk(x,y)){
                if(dp[x][y]!=-1) return dp[x][y];
                int curr = matrix[x][y], mx=0;
                if(isOk(x-1, y) && curr < matrix[x-1][y]){
                    mx = max(mx, dfs(matrix, x-1, y, dp));
                }
                if(isOk(x, y-1) && curr < matrix[x][y-1]){
                    mx = max(mx, dfs(matrix, x, y-1, dp));
                }
                if(isOk(x+1, y) && curr < matrix[x+1][y]){
                    mx = max(mx, dfs(matrix, x+1, y, dp));
                }
                if(isOk(x, y+1) && curr < matrix[x][y+1]){
                    mx = max(mx, dfs(matrix, x, y+1, dp));
                }
                dp[x][y]=mx+1;
                return mx+1;
            }else{
                return 0;
            }
        }
        int longestIncreasingPath(vector<vector<int>>& matrix) {
            int ret = 0;
            m = matrix.size();
            if(m==0) return 0;
            n = matrix[0].size();
            vector<vector<int>> dp(m, vector<int>(n, -1));
            for(int x=0;x<m;x++){
                for(int y=0;y<n;y++){
                    if(dp[x][y]==-1){
                        ret = max(ret, dfs(matrix, x, y, dp));
                    } else {
                        ret = max(ret, dp[x][y]);
                    }
                }
            }
            return ret;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.