Clean and easy 43ms O(mn) java code


  • 0
    L
    public class Solution {
    int [][] map;
    int [][] dp;
    public int longestIncreasingPath(int[][] matrix) {
        int m = matrix.length;
        if(m < 1)
            return 0;
        int n = matrix[0].length;
        map = new int [m + 2][n + 2];
        dp = new int[m + 2][n + 2];
        for(int i = 0; i < m; i ++) {
            map[i + 1][0] = map[i + 1][n + 1] = 0x7fffffff;
            dp[i + 1][0] = dp[i + 1][n + 1] = 0;
            for(int j = 0; j < n; j ++) {
                map[0][j + 1] = map[m + 1][j + 1] = 0x7fffffff;
                dp[0][j + 1] = dp[m + 1][j + 1] = 0;
                map[i + 1][j + 1] = matrix[i][j];
                dp[i + 1][j + 1] = 0;
            }
        }
        int ret = 0;
        for(int i = 0; i < m; i ++)
            for(int j = 0; j < n; j ++)
                ret = Math.max(ret, dfs(i + 1, j + 1, m, n));
        return ret;
    }
    
    public int dfs(int i, int j, int m, int n) {
        if(i == 0 || j == 0 || i == m + 1 || j == n + 1)
            return 0;
        if(dp[i][j] > 0)
            return dp[i][j];
        int ret = 1;
        if(map[i][j] > map[i - 1][j])
            ret = Math.max(ret, dfs(i - 1, j, m, n) + 1);
        if(map[i][j] > map[i + 1][j])
            ret = Math.max(ret, dfs(i + 1, j, m, n) + 1);
        if(map[i][j] > map[i][j - 1])
            ret = Math.max(ret, dfs(i, j - 1, m, n) + 1);
        if(map[i][j] > map[i][j + 1])
            ret = Math.max(ret, dfs(i, j + 1, m, n) + 1);
        dp[i][j] = ret;
        return ret;
    }
    

    }


Log in to reply
 

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