Share my solution using dfs with memorization


  • 0
    O
    class Solution {
        int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
        int solve(int x, int y, vector<vector<int>>& matrix, vector<vector<int>>& dp) {
            if (dp[x][y] != -1) return dp[x][y];
            int ans = 1;
            for (int k = 0; k < 4; k++) {
                int nx = dx[k] + x, ny = dy[k] + y;
                if (nx < 0 || ny < 0 || nx >= matrix.size() || ny >= matrix[0].size()) continue;
                if (matrix[nx][ny] > matrix[x][y]) ans = max(ans, solve(nx, ny, matrix, dp) + 1);
            }
            return dp[x][y] = ans;
        }
    public:
        int longestIncreasingPath(vector<vector<int>>& matrix) {
            if (matrix.size() <= 0 || matrix[0].size() <= 0) return 0;
            int M = matrix.size(), N = matrix[0].size();
            vector<vector<int> > dp (M, vector<int>(N, -1));
            int ans = 0;
            for (int i = 0; i < M; i++) for (int j = 0; j < N; j++) ans = max(ans, solve(i, j, matrix, dp));
            return ans;
        }
    };

Log in to reply
 

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