My Java solution using DP with memorization (beats about 98% submissions)


  • 3
    public int minPathSum(int[][] grid) {
        int[][] memo = new int[grid.length][grid[0].length];
        return minPathSumHelper(grid, 0, 0, memo);
    }
    
    public int minPathSumHelper(int[][] grid, int row, int col, int[][] memo) {
        if(row == grid.length-1 && col == grid[0].length-1) return grid[row][col];
        if(memo[row][col] != 0) return memo[row][col];
    
        int rowInc = Integer.MAX_VALUE, colInc = Integer.MAX_VALUE;
        if(row < grid.length-1) rowInc = minPathSumHelper(grid, row+1, col, memo);
        if(col < grid[0].length-1) colInc = minPathSumHelper(grid, row, col+1, memo);
        memo[row][col] = Math.min(rowInc, colInc) + grid[row][col];
        return memo[row][col];
    }
    

    Use a 2D array named memo to remember value which is calculated before to speed up.


  • 0
    W

    This is a method to find the minimum sum from the last index of the matrix. I wonder why it runs so fast?


  • 0
    L

    I wonder too!


  • 0
    F

    I would like to know why this is faster than other DP methods.


Log in to reply
 

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