063.UniquePathsII.md

63. Unique Paths II

Question:

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.

Example:

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

Analysis:

这道题是动态规划的题目：

采用动态规划法，动态规划利用上一次的结果，特殊的迭代思想，动态规划的关键是要得到递推关系式

达到某一点的路径等于到达它上一点的路径数与它左边的路径数之和。

用ways[i][j]表示起点到点(i,j)的路径总数；并且ways[i][j]=ways[i][j-1]+ways[i-1][j]

这道题里面给机器人加了障碍物 如果棋盘 obstacleGrid[i][j-1]== 0

那么ways[i][j] += ways[i-1][j]

要么往上要么往右首先初始化第一排和第一列， 为1，1

Solution C++:

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if (obstacleGrid.size() == 0)
            return 0;
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        vector<vector<int>> ways(m, vector<int>(n, 0)); //先行后列
        int i = 0, j = 0;
        //1表示只有一条路
        while (i < m && ! obstacleGrid[i][0])
            ways[i++][0] = 1;
        while (j < n && ! obstacleGrid[0][j])
            ways[0][j++] = 1;
        i = 1 ;
        while ( i < m ){
            j = 1 ;
            while( j < n ){
                if ( ! obstacleGrid[i][j] ) {
                    if ( ! obstacleGrid[i - 1][j] )
                        ways[i][j] += ways[i - 1][j];
                    if ( ! obstacleGrid[i][j - 1] )
                        ways[i][j] += ways[i][j - 1];                    
                }
                j = j + 1;
            }
            i = i + 1;        
        }
        return ways[m - 1][n - 1];
    }
};

本题关键：

动态规划