Unique Paths II(动态规划)
Unique Paths II
更多技术博客 http://vilins.top/
题目
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:
- Right -> Right -> Down -> Down
- Down -> Down -> Right -> Right
分析
这里是典型的动态规划问题，通过将大问题分解为小问题来不断求解。
我们这里用本来的二维数组作为存储结果的数组，那我们分析一下这样使用的可用性，在对原始obstacleGrid[i][j]使用之前，我们只会使用前面的obstacleGrid[i-1][j]和obstacleGrid[i][j-1]的数据，所以我们这样使用不会改变初始数据，并且可以节省空间。
其次，我们来看看状态转移方程，我们用的二维数组表示的时，当前这个点之前可以选择的所有路径，由于路径的选择只有向下和向右这两个方向，如果当前格子有障碍物的话，到当前格子的路径数为0，那么我们得出以下状态转移方程：
if(obstacleGrid[i][j] == 0) { obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]; } else { obstacleGrid[i][j] = 0; }源码
class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int row = obstacleGrid.size(); int col = obstacleGrid[0].size(); if(row == 0||col == 0) { return 0; } if(obstacleGrid[0][0] == 1) { return 0; } obstacleGrid[0][0] = 1; for(int i = 1; i < row; i++) { if(obstacleGrid[i][0] == 0) { obstacleGrid[i][0] = obstacleGrid[i-1][0]; } else { obstacleGrid[i][0] = 0; } } for(int i = 1; i < col; i++) { if(obstacleGrid[0][i] == 0) { obstacleGrid[0][i] = obstacleGrid[0][i-1]; } else { obstacleGrid[0][i] = 0; } } for(int i = 1; i < row; i++) { for(int j = 1; j < col; j++) { if(obstacleGrid[i][j] == 0) { obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]; } else { obstacleGrid[i][j] = 0; } } } return obstacleGrid[row-1][col-1]; } };