Java 3 solutions: Recursion, Memoization, DP


  • 0
    M
    1. Plain recursion
    class Solution {
        int[][] matrix;
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            
            matrix = obstacleGrid;
            
            if(matrix.length == 0 || matrix[0].length == 0 || matrix[0][0] ==  1) {
                return 0;
            }
            return paths(matrix.length-1, matrix[0].length-1);
            
        }
        
        private int paths(int m, int n){
            
            if(m == 0 && n == 0) return 1;
            
            if(m<0 || n<0 || matrix[m][n] == 1) return 0;
            
            return paths(m-1,n)+paths(m,n-1);
            
        }
    }
    
    
    1. Memoization
    class Solution {
        int[][] matrix;
        Map<String, Integer> cache;
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            
            matrix = obstacleGrid;
            cache = new HashMap<String, Integer>();
            
            if(matrix.length == 0 || matrix[0].length == 0 || matrix[0][0] ==  1) {
                return 0;
            }
            return paths(matrix.length-1, matrix[0].length-1);
            
        }
        
        private int paths(int m, int n){
            String str = m + "," + n;
            
            if(cache.containsKey(str)){
                return cache.get(str);
            }
            
            if(m == 0 && n == 0) return 1;
            
            if(m<0 || n<0 || matrix[m][n] == 1) return 0;
            
            cache.put(str, paths(m-1,n)+paths(m,n-1));
            
            return cache.get(str);
        }
    }
    
    
    1. DP
    class Solution {
       
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            
           if(obstacleGrid.length==0 || obstacleGrid[0].length==0 ) {
               return 0;
           }
           
           int m=obstacleGrid.length;
           int n=obstacleGrid[0].length;
           
            int dp[][] = new int[m][n];
           
            if(obstacleGrid[0][0]==1 || obstacleGrid[m-1][n-1]==1) {
                return 0;
            }
            
            dp[0][0]=1;
            
            for(int i=1; i<m; i++) {
                
                if (obstacleGrid[i][0]==1) {
                    dp[i][0]=0;
                } else {
                    dp[i][0]=dp[i-1][0];
                }
            }
            
            for(int j=1; j<n; j++){
                
                if(obstacleGrid[0][j]==1) {
                    dp[0][j]=0;
                }
                else {
                    dp[0][j]=dp[0][j-1];
                }
            }
            
            for(int i=1; i<m; i++) {
                for(int j=1; j<n; j++) {
                    
                    if(obstacleGrid[i][j]==1) {
                        dp[i][j]=0;
                    }
                    else {
                        dp[i][j]=dp[i-1][j]+dp[i][j-1];
                    }
                }
            }
            
            return dp[m-1][n-1];
        }
       
    }
    

Log in to reply
 

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