[Leetcode刷题总结系列][Dynamic Programming]63. Unique Paths II

港控/mmm° 2022-07-24 10:27 139阅读 0赞

# Unique Paths II #

Follow up for “Unique Paths”:

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

An obstacle and empty space is marked as `1` and `0` respectively in the grid.

For example,  
There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
    [0,0,0],
    [0,1,0],
    [0,0,0]
    ]

The total number of unique paths is `2`.

类似于Unique path，这道题也用动态规划解决。那么对于某一点的路径数量，仍然符合公式：  
`path[i][j] = path[i-1][j] + path[i][j-1]`。  
与之前不同的是，此次需要考虑遇到障碍物的情况。显而易见，障碍物处对应的路径数量应该为0。同时，还要考虑到边界情况。比如`[[0]]`和`[[1]]`。并且对于第一行和第一列的点，障碍物之后和障碍物之下的路径数量都应该为0。  
这道题同样可以只用`O(n)`空间解决，由于我们从左向右，从上向下计算，所以该数组应当从左向右被新值覆盖，既：`path[i] += path[i-1]`  
由此可以得到以下代码：

该段代码的运行时间为`O(m*n)`，空间复杂度为`O(n)`

public class Solution {
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            /*
            Dynamic Programming
            Every point in the grid has two approaches to reach, either from above or from left point. So
            a way to reach a given point is numofpath[i][j] = numofpath[i][j-1] + numofpath[i-1][j]
            However, consider that there is obstacles in this grid, we should let the numofpath of those
            points whose value is 1(obstacle) to be 0 since they cannot be passed. 
            At the same time, since we don't need to reconstruct the path, we only need to keep track of
            the current row we are calculating. And based on the function above, we have to calculat from
            left to right and replace old values gradually. 
            Then the last one of the array, after the whole loop ends, is what we need. 
            O(m*n) time and O(n) space.
            */
            if (obstacleGrid == null || obstacleGrid.length == 0){
                return 0;
            }
    
            int l = obstacleGrid[0].length; //the number of grids in one row
            int h = obstacleGrid.length; // the number of rows.
            int[] numofpath = new int[l];
    
            //initialize the array. if there is only one row in the grid, then all points on the right
            side of the obstacle have 0 path to reach.
            //if there is only one point in the grid, we have to consider if it is a obstacle or not. 
            numofpath[0] = obstacleGrid[0][0] == 1? 0 : 1;
            for (int i = 0; i < h; i++){
                // the first column of points can only have paths if this point is not an obstacle and
                its above rows have paths.
                numofpath[0] = (obstacleGrid[i][0] == 0) && (numofpath[0] != 0)? 1 : 0;
                for (int j = 1; j < l; j++){
                    if (obstacleGrid[i][j] == 0){ //there is no obstacle on this grid
                        numofpath[j] += numofpath[j-1];
                    }
                    if(obstacleGrid[i][j] == 1){ //there is an obstacle on this grid
                        numofpath[j] = 0;
                    }
                }
            }
    
            return numofpath[l-1];
    
        }
    
    }