63. Unique Path II

Now consider if some obstacles are added to the grids. How many unique paths would there be?

iteration: brief solution using additional memory:

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid[0].length;
        int[] rowMemo = new int[n];
        rowMemo[0]=1;
        for (int[] row : obstacleGrid){
            for(int i = 0; i< n; i++){
                
                // it also resovle the i==0 case:
                // path from [0][0] to [x][0] is either 1 or 0
                // once path is 0, the next one [x+1][0] is always 0
                if (row[i] == 1) 
                    rowMemo[i]=0;
                else if (i>0)
                    rowMemo[i]+=rowMemo[i-1];
            }
        }
        return rowMemo[n-1];
    }
}

recursion: not recommended, as the original values of the grid need to be revised;

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        
        for(int i=0; i<m; i++){
            for (int j=0;j<n; j++){
                //if obstacle, the value is -1;
                //if not visited, the value is -2;
                obstacleGrid[i][j] -= 2;
            }
        }
        return recursion(m-1, n-1, obstacleGrid);     
    }
    
    private int recursion(int m, int n, int[][] grid){
        if (grid[m][n]>=0) return grid[m][n]; 
        if (grid[m][n]==-1) return 0;

        if (m == 0 && n == 0){
            if (grid[m][n] == -2) grid[m][n]=1;
            return grid[m][n];
        }else if (m == 0){
            grid[m][n] = recursion(m, n-1, grid);
            return grid[m][n];
        }else if (n == 0){
            grid[m][n] = recursion(m-1, n, grid);
            return grid[m][n];
        }
        grid[m][n] = recursion(m-1, n, grid)+recursion(m, n-1, grid);
        return grid[m][n];  
    }
}