之所以将这三道题放在一起，是因为这三道题非常类似。
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]表示从左上角到grid[i][j]的最小路径和。那么dp[i][j] = grid[i][j] + min( dp[i-1][j], dp[i][j-1] );
下面的代码中，为了处理计算第一行和第一列的边界条件，我们令dp[i][j]表示从左上角到grid[i-1][j-1]的最小路径和，最后dp[rows][cols]是我们所求的结果
int minPathSum(vector<vector<int>>& grid) {
int rows = grid.size();
if(rows == )
return ;
int cols = grid[].size();
vector<vector<int> > dp(rows + , vector<int>(cols + , INT_MAX));
dp[][] = ;
for(int i = ; i < rows + ; i++)
for(int j = ; j < cols + ; j++)
dp[i][j] = grid[i - ][j - ] + min(dp[i][j - ], dp[i - ][j]);
return dp[rows][cols];
}
注意到上面的代码中dp[i][j] 只和上一行的dp[i-1][j]和上一列的dp[i][j-1]有关，因此可以优化空间为O（n）（准确来讲空间复杂度可以是O（min（row,col）））
int minPathSum(vector<vector<int>>& grid) {
int rows = grid.size();
if(rows == )
return ;
int cols = grid[].size();
vector<int> dp(cols + , INT_MAX);
dp[] = ;
for(int i = ; i < rows + ; i++)
for(int j = ; j < cols + ; j++)
dp[j] = grid[i-][j-] + min(dp[j-], dp[j]);
return dp[cols];
}
2. 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?
Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
这道题的解答跟上一道题是非常类似的，程序如下：
int uniquePaths(int m, int n) {
if(m == && n == )
return ;
vector<vector<int> > dp(m, vector<int>(n, ));
for(int i = ; i < m; i++)
for(int j = ; j < n; j++)
dp[i][j] = dp[i-][j] + dp[i][j-];
return dp[m-][n-];
}
优化空间程序：
int uniquePaths(int m, int n) {
if(m == && n == )
return ;
vector<int> dp(n, );
for(int i = ; i < m; i++)
for(int j = ; j < n; j++)
dp[j] = dp[j-] + dp[j];
return dp[n - ];
}
3. Unique Paths II
题目要求：
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.
[
[,,],
[,,],
[,,]
]
The total number of unique paths is 2.
Note: m and n will be at most 100.
这道题跟上一道题基本一致，不同的地方在于我们需要将能到达存在obstacle的地方的路径数置为0。程序如下：
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int rows = obstacleGrid.size();
if(rows == )
return ;
int cols = obstacleGrid[].size();
if(cols == )
return ;
vector<vector<int> > dp(rows, vector<int>(cols, ));
int i = ;
while(i < rows)
{
if(obstacleGrid[i][] == )
while(i < rows)
{
dp[i][] = ;
i++;
}
i++;
}
int j = ;
while(j < cols)
{
if(obstacleGrid[][j] == )
while(j < cols)
{
dp[][j] = ;
j++;
}
j++;
}
for(i = ; i < rows; i++)
for(j = ; j < cols; j++)
{
if(obstacleGrid[i][j] == )
dp[i][j] = ;
else
dp[i][j] = dp[i-][j] + dp[i][j-];
}
return dp[rows-][cols-];
}