## Monday, November 24, 2014

### [LeetCode] Unique Paths I, II

Unique Paths I

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?
Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.

Unique Paths II

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`.
Note: m and n will be at most 100.

Climbing Stairs二维版。计算解个数的题多半是用DP。而这两题状态也非常显然，dp[i][j]表示从起点到位置(i, j)的路径总数。DP题目定义好状态后，接下去有两个任务：找通项公式，以及确定计算的方向。

1. 由于只能向右和左走，所以对于(i, j)来说，只能从左边或上边的格子走下来：
dp[i][j] = dp[i-1][j] + dp[i][j-1]

2. 对于网格最上边和最左边，则只能从起点出发直线走到，dp[0][j] = dp[i][0] = 1

3. 计算方向从上到下，从左到右即可。可以用滚动数组实现。

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13``` ```class Solution { public: int uniquePaths(int m, int n) { if(m<1 || n<1) return 0; vector dp(n, 1); for(int i=1; i

1. 当(i, j)有障碍时dp[i][j] = 0
2. dp[0][j]和dp[i][0]未必为1.
dp[0][j] = obstacleGrid[0][j] ? 0 : dp[0][j-1]
dp[i][0] = obstacleGrid[i][0] ? 0 : dp[i-1][0]
3. 当obstacleGrid [0][0] = 1时，return 0

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22``` ```class Solution { public: int uniquePathsWithObstacles(vector > &obstacleGrid) { if(obstacleGrid.empty() || obstacleGrid[0].empty() || obstacleGrid[0][0]==1) return 0; int m = obstacleGrid.size(), n = obstacleGrid[0].size(); vector dp(n,1); for(int j=1; j