63. Unique Paths II-Leetcode
2018-01-18 本文已影响5人
analanxingde
与上一题相比
不同之处在于有了obstacle,差别在于到每个obstacle的可能路径个数为0。
用一个dp数组来维护每一行便利完之后的路径个数,只是在更新dp数组时需要考虑obstacleGrid数组相应位子的值是否为0
我的AC代码
class Solution {
//如果obstacles的值为1,则此位置的值设为0
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m=obstacleGrid.size();//行数
int n=obstacleGrid[0].size();//列数
vector<int> dp(n+1,0);
dp[1]=1;
for(int i=0;i<m;i++)//
for(int j=1;j<=n;j++)
{
if(obstacleGrid[i][j-1]==1)
dp[j]=0;
else
dp[j]+=dp[j-1];
}
return dp.back();
}
};
最优解
时间上优于我的解法(目前还没找到原因),空间上没有单数组维护申请的额外空间少
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid.at(0).size();
int path[m + 1][n + 1];
for (int i = 0; i < (m + 1); i++) path[i][0] = 0;
for (int i = 0; i < (n + 1); i++) path[0][i] = 0;
for (int i = 1; i < (m + 1); i++) {
for (int j = 1; j < (n + 1); j++) {
if (obstacleGrid.at(i - 1).at(j - 1) == 1) path[i][j] = 0;
else {
if ((i == 1) && (j == 1)) {
path[i][j] = 1;
} else {
path[i][j] = path[i - 1][j] + path[i][j - 1];
}
}
}
}
return path[m][n];
}
};