Java clean memorization code, O(m*n) time and space


  • 2
    Y

    This is the 2d version LIS problem, thinking it from the reverse direction is easier for me. I used a m*n array to save the middle result. dp[x][y] = Math.max(dp[x][y], search(matrix, dp, nx, ny) + 1); is the core code to realize the search, basically we either inherit the previous search result or add one to the recursive call. Hope it helps and any suggestion to improve it is welcome!

    Edit: Modify the logic a bit to make it clearer. This is very nice problem, worth thinking through. The method can be easily extended a few other problems.

    int m, n;
    int[][] direction = {{1,0},{-1,0},{0,1},{0,-1}};
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix == null || (m = matrix.length) == 0 || (n = matrix[0].length) == 0) {
            return 0;
        }
        int best = 0;
        int[][] dp = new int[m][n];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                best = Math.max(best, helper(matrix, dp, i, j));
            }
        }
        return best;
    }
    
    private int helper(int[][] matrix, int[][] dp, int i, int j) {
        if(dp[i][j] > 0) {
            return dp[i][j];
        }
        dp[i][j] = 1;
        for(int[] d : direction) {
            int x = i + d[0];
            int y = j + d[1];
            if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
                int dis = helper(matrix, dp, x, y) + 1;
                dp[i][j] = Math.max(dp[i][j], dis);
            }
        }
        return dp[i][j];
    }

  • 1

    nice solution! But I think the logic would be more clear if
    matrix[nx][ny] > matrix[x][y]. when matrix[x][y] is smaller than its neighbor, it can go to the neighbor first and then continue the search, therefore path length is dp[nx][ny] + 1. although "<" works too.
    int max = 0 is never used and can be removed.


Log in to reply
 

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