leetcode [Dynamic Programming] No.63 Unique Path II

问题描述

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

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.

Note: m and n will be at most 100.

Example 1:

Input:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:

1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

解题思路

这是一个典型的动态规划问题：我们可以维护一个和地图一样大小的二维数组，数组的相应位置存储的是到当前位置所存在的路径数量。那么对于一个格子$(i, j)$(i,j)，如果这个格子中没有障碍物，则可到达这个格子的路径数量$C_{i,j} = C_{i-1,j} + C_{i,j-1}$Ci,j​=Ci−1,j​+Ci,j−1​，因为我们只可以往下走和往右走，换而言之，一个格子只可能从它左边的格子或者上面的格子到达，所以可到达路径数量就是左边格子和上面格子的可到达路径数量之和。对于一个有障碍物的格子，我们把它的可到达路径数量设为0。当然，我们需要注意在计算最左边一列和最上面一行不要访问越界。那么最后的答案自然就是目标格子（最右下角的格子）的可到达路径数量。

代码：

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        vector<vector<int>> count;
        int height = obstacleGrid.size();
        int width = obstacleGrid[0].size();
        for (int i = 0; i < height; i++) {
            count.push_back(vector<int>(width, 0));
        }
        count[0][0] = 1;
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (obstacleGrid[i][j] == 1) {
                    count[i][j] = 0;
                } else {
                	if (i > 0) count[i][j] += count[i-1][j];
                	if (j > 0) count[i][j] += count[i][j-1];
                }
            }
        }
        return count[height-1][width-1];
    }
};

运行结果：

因为我们只访问了一遍二维数组，所以该动态规划算法的效率为$O(m * n)$O(m∗n)。