Java Easy to understand 10 lines


  • 2

    This implementation uses Memoization Dynamic programming. This solution sacrifices space for simplicity. For me this is easier to understand and follow; in part because it is a popular/standard memorization pattern. Some simple optimizations can be made but i have elected to leave them out for a more simple solution.

    public class Solution {
        public int minPathSum(int[][] grid) {
            Integer[][] memo = new Integer[grid.length][grid[0].length];
            return minPath(memo,grid,0,0);
        }
        private int minPath(Integer[][] memo, int[][] grid, int row, int col){
            if(row >= grid.length || col >= grid[0].length) return Integer.MAX_VALUE;
            if(row == grid.length-1 && col == grid[0].length-1) return grid[row][col];
            if(memo[row][col] == null) memo[row][col] = Math.min(minPath(memo,grid,row+1,col),minPath(memo,grid,row,col+1)) + grid[row][col];
            return memo[row][col];            
        }
    }

  • 0
    M

    I implemented this solution in the same way, but using a memo matrix of primitive ints, which is better in terms of memory usage but at the same time requires me to fill with -1s. Thanks for sharing!


Log in to reply
 

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