Java 3 solutions: Recursion, Memoization, DP


  • 0
    M
    1. Plain Recursion
    class Solution {
        
        int[][] matrix;
        
        public int minPathSum(int[][] grid) {
            matrix = grid;
            
            if(grid.length == 0 || grid[0].length == 0) return 0;
            
            return path(0,0);
            
        }
        
        private int path(int i, int j) {
            
            if(i==matrix.length-1 && j==matrix[0].length-1){
                return matrix[i][j];
            }
            
            if(i >= matrix.length || j >= matrix[0].length) {
                return Integer.MAX_VALUE;
            }
            
            return Math.min(path(i+1,j), path(i,j+1)) + matrix[i][j];
            
        }
    }
    
    
    1. Memoization
    class Solution {
        
        int[][] matrix;
        Map<String, Integer> cache;
        
        public int minPathSum(int[][] grid) {
            matrix = grid;
            cache = new HashMap<String, Integer>();
            if(grid.length == 0 || grid[0].length == 0) return 0;
            
            return path(0,0);
            
        }
        
        private int path(int i, int j) {
            
            String str = i+","+j;
            
            if(i==matrix.length-1 && j==matrix[0].length-1){
                return matrix[i][j];
            }
            
            if(i >= matrix.length || j >= matrix[0].length) {
                return Integer.MAX_VALUE;
            }
            
            if(cache.containsKey(str)){
                return cache.get(str);
            }
            
            int l=Integer.MAX_VALUE; int r = Integer.MAX_VALUE;
            
            l = path(i+1, j);
            r = path(i, j+1);
            
            cache.put(str, Math.min(l,r) + matrix[i][j]);
            
            return cache.get(str);
            
        }
    }
    
    1. DP
    class Solution {
        public int minPathSum(int[][] grid) {
            
            if(grid.length == 0 || grid[0].length == 0) return 0;
            
            int[][] dp = new int[grid.length][grid[0].length];
            
            dp[0][0] = grid[0][0];
            
            for(int i=1; i<grid.length; i++){
                dp[i][0] = dp[i-1][0] + grid[i][0];
            }
            
            for(int j=1; j<grid[0].length; j++){
                dp[0][j] = dp[0][j-1] + grid[0][j];
            }
            
            for(int i=1; i<grid.length; i++) {
                
                for(int j=1; j<grid[0].length; j++){
                    
                    dp[i][j] = Math.min(dp[i][j-1], dp[i-1][j]) + grid[i][j];
                    
                }
                
            }
            
            return dp[grid.length-1][grid[0].length-1];
            
        }
    }
    
    

Log in to reply
 

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