Java Memorization DP


  • 0
    Y

    The longest path relies on the adjacent ones that's smaller. And the memorization is for reducing the repeating DFS to get the longest path for visited position again. Here is the code:

    public class Solution {
        int[][] delta = {{1, 0},{-1, 0},{0, 1},{0, -1}}, mem;
        
        public int longestIncreasingPath(int[][] matrix) {
            int max = 0;
            if (matrix.length > 0) {
                mem = new int[matrix.length][matrix[0].length];
                for (int y = 0; y < matrix.length; ++y) {
                    for (int x = 0; x < matrix[y].length; ++x) {
                        max = Math.max(max, _longestIncreasingPath(matrix, x, y));
                    }
                }
            }
            return max;
        }
    
        public int _longestIncreasingPath(int[][] matrix, int x, int y) {
            if (mem[y][x] == 0) {
                mem[y][x] = 1;
                for (int k = 0; k < delta.length; ++k) {
                    int nextX = x + delta[k][0];
                    int nextY = y + delta[k][1];
                    if (nextX >= 0 && nextY >= 0 && 
                        nextX < matrix[0].length && nextY < matrix.length) {
                        if (matrix[nextY][nextX] < matrix[y][x]) {
                            mem[y][x] = Math.max(mem[y][x], _longestIncreasingPath(matrix, nextX, nextY) + 1);
                        }
                    }
                }
            }
            return mem[y][x];
        }
    }

Log in to reply
 

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