# Unique Paths

> 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?

`dp[i][j] = dp[i - 1][j] + dp[i][j - 1]`

dp[i][j]表示从点(0, 0)到(i, j)唯一路径数量。

```c++
class Solution {
public:
int uniquePaths(int m, int n) {
int dp[m][n];
//初始化dp，m x 1情况全为1
for(int i = 0; i < m; i++) {
dp[i][0] = 1;
}

//初始化dp，1 x n情况全为1
for(int j = 0; j < n; j++) {
dp[0][j] = 1;
}

for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}

return dp[m - 1][n - 1];
}
};
```

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

```c++
class Solution {
public:
int uniquePathsWithObstacles(vector > &obstacleGrid) {
if(obstacleGrid.empty() || obstacleGrid[0].empty()) {
return 0;
}

int m = obstacleGrid.size();
int n = obstacleGrid[0].size();

int dp[m][n];

//下面初始dp的时候需要根据obstacleGrid的值来确定
dp[0][0] = (obstacleGrid[0][0] == 0 ? 1 : 0);

//我们需要注意m x 1以及1 x n的初始化
for(int i = 1; i < m; i++) {
dp[i][0] = ((dp[i - 1][0] == 1 && obstacleGrid[i][0] == 0) ? 1 : 0);
}

for(int j = 1; j < n; j++) {
dp[0][j] = ((dp[0][j - 1] == 1 && obstacleGrid[0][j] == 0) ? 1 : 0);
}

for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
if(obstacleGrid[i][j] == 1) {
dp[i][j] = 0;
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}

return dp[m - 1][n - 1];
}
};
```

# Minimum Path Sum

> Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

> Note: You can only move either down or right at any point in time.

`dp[i][j] = min(dp[i][j-1], dp[i - 1][j]) + grid[i][j]`

```c++
class Solution {
public:
int minPathSum(vector > &grid) {
if(grid.empty() || grid[0].empty()) {
return 0;
}

int row = grid.size();
int col = grid[0].size();

int dp[row][col];

dp[0][0] = grid[0][0];
for(int i = 1; i < row; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}

for(int j = 1; j < col; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}

for(int i = 1; i < row; i++) {
for(int j = 1; j < col; j++) {
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}

return dp[row - 1][col - 1];
}
};
```