博文中会简要介绍Leetcode P0063题目分析及解题思路。
“Unique Paths II”是p0062的变形题。递推式十分简单，但是题目本身属于原型题，很多动态规划或者各种算法组合的题目是出自于它的。
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.
这道题的思路很直接明了。递推式如下：
令dp[i][j]表示到第i行第j列的位置所有不同的路径走法
dp[0][0] = 1
dp[i][j] = 0, if map[i][j] == 1
被阻挡则没有任何路径可达
dp[i][0] = dp[i-1][0]
dp[0][j] = dp[0][j-1]
边界只有一条路，或被阻挡
dp[i][j] = dp[i-1][j]+dp[i][j-1], if map[i][j] != 1
任何一个位置等于来自上面的走法和来自左边的走法之和。
以下是Java的题解代码实现。
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid == null
|| obstacleGrid.length == 0
|| obstacleGrid[0][0] == 1)
return 0;
int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = 1;
for (int itr=1; itr<m; ++itr) {
if (obstacleGrid[itr][0] == 1)
dp[itr][0] = 0;
else
dp[itr][0] = dp[itr-1][0];
}
for (int itr=1; itr<n; ++itr) {
if (obstacleGrid[0][itr] == 1)
dp[0][itr] = 0;
else
dp[0][itr] = dp[0][itr-1];
}
for (int i1=1; i1<m; ++i1) {
for (int j2=1; j2<n; ++j2) {
if (obstacleGrid[i1][j2] == 1)
dp[i1][j2] = 0;
else
dp[i1][j2] = dp[i1-1][j2]+dp[i1][j2-1];
}
}
return dp[m-1][n-1];
}
}
以下是C++的题解代码实现。
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
if (obstacleGrid.size() == 0
|| obstacleGrid[0][0] == 1)
return 0;
int m = obstacleGrid.size(), n = obstacleGrid[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
dp[0][0] = 1;
for (int itr=1; itr<m; ++itr) {
if (obstacleGrid[itr][0] == 1)
dp[itr][0] = 0;
else
dp[itr][0] = dp[itr-1][0];
}
for (int itr=1; itr<n; ++itr) {
if (obstacleGrid[0][itr] == 1)
dp[0][itr] = 0;
else
dp[0][itr] = dp[0][itr-1];
}
for (int i1=1; i1<m; ++i1) {
for (int j2=1; j2<n; ++j2) {
if (obstacleGrid[i1][j2] == 1)
dp[i1][j2] = 0;
else
dp[i1][j2] = dp[i1-1][j2]+dp[i1][j2-1];
}
}
return dp[m-1][n-1];
}
};