题目

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).

How many possible unique paths are there?

img

Above is a 3 x 7 grid. How many possible unique paths are there?

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.

1
2
3
4
5
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

大意

从一个位置走到另一个位置，中间有障碍，问一共有多少种走法。62题的升级版。

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& grid) {
        if(grid.empty()) return 0;
        int hang=grid.size();
        int lie=grid[0].size();
        vector<vector<int>> dp(hang, vector<int>(lie,0));
        int flag=1;
        int k;
        for(k=0;k<hang;k++)
        {
            if(grid[k][0]!=1)
            {
                dp[k][0]=1;
            }
            else
            {
                break;
            }
        }
        for(;k<hang;k++)
        {
            dp[k][0]=0;
        }
        for(k=0;k<lie;k++)
        {
            if(grid[0][k]!=1)
            {
                dp[0][k]=1;
            }
            else
            {
                break;
            }
        }
         for(;k<lie;k++)
        {
            dp[0][k]=0;
        }
        for(int i=1;i<hang;i++)
        {
            for(int j=1;j<lie;j++)
            {
                if(grid[i][j]!=1) // 去掉障碍物。
                {
                     dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[hang-1][lie-1];
    }
};

思路

使用动态规划，声明一个hang lie大小的数组，每个位置表示到这个位置有多少种走法，没有障碍物的时候，可以知道对于一个 hang lie 大小的矩阵，第一行所有数都是1,第一列所有数都是1,因为都是只有一种走法，对于其他位置，状态转移方程是dp[i][j]=dp[i][j-1]+dp[i-1][j],也就是说每一个点的位置等于它上面的数加上左边的数的和，通过这样写出状态转移方程，然后从头遍历到尾即可。

加强版

添加了障碍后，有了一个变化，那就是在第一列或者第一行中，只要有一个障碍物，那个障碍物的那个点能到的步数为0，这个点后面的所有地方能到的也为0，所以在赋值的时候需要特殊处理。

然后在遍历的时候也要去掉障碍物。

tips

声明一个n个大小的vector<vector >
vector<vector > res( n, vector(n) );