C++ short solution


  • 0
    P
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.size() == 0) return 0;
        int ans = 0;
        vector<vector<int>> dp(matrix.size(), vector<int> (matrix[0].size(), 1));
        for (int i = 0; i < matrix.size(); i++) for (int j = 0; j < matrix[0].size(); j++) ans = max(ans, dfs(i, j, matrix, dp));
        return ans;
    }
    
    int dfs(int i, int j, vector<vector<int>>& matrix, vector<vector<int>>& dp) {
        if (dp[i][j] != 1) return dp[i][j];
        if (i > 0 && matrix[i - 1][j] < matrix[i][j]) dp[i][j] = max(dp[i][j], dfs(i - 1, j, matrix, dp) + 1);
        if (i < matrix.size() - 1 && matrix[i + 1][j] < matrix[i][j]) dp[i][j] = max(dp[i][j], dfs(i + 1, j, matrix, dp) + 1);
        if (j > 0 && matrix[i][j - 1] < matrix[i][j]) dp[i][j] = max(dp[i][j], dfs(i, j - 1, matrix, dp) + 1);
        if (j < matrix[0].size() - 1 && matrix[i][j + 1] < matrix[i][j]) dp[i][j] = max(dp[i][j], dfs(i, j + 1, matrix, dp) + 1);
        return dp[i][j];
    }

Log in to reply
 

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