文档介绍：靖空间
效苏秦,闭关修炼! 吾破关之日,就是中国横添一颗计算机星级人才之
日!
LeetCode Unique Paths II
分类: Algorithm算法 2013-12-17 08:17 268人阅读评论(0) 收藏举报
LeetCodeUnique Paths II
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.
[
[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.
和Unique PathsI差不多,不过增加了一个判断条件,如果有障碍的话,那么这个格就填写0,表示0个路径。
不过做这道题还是有点麻烦的:
1 需要初始化动态规划法表的第一行
2 每次需要更新表的第一个格
不过也可以简单点,如果使用额外的一个存储空间,可以少一个判断条件。LeetCode上有程序是这么写的。
不过我这里是不使用额外空间,增加一个判断(程序中注意的地方)就可以了,从简洁度来说,好像也差不多。看
各人喜欢了。
class Solution {
public:
//头脑考虑问题不够全面就会有bug,需要严谨的逻辑思维
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
int r = ();
if (r < 1) return 1;
int c = obstacleGrid[0].size();
vector<int> table(c);
if (obstacleGrid[0][0] == 1) return 0;
else table[0] = 1;
for (int i = 1; i < c && obstacleGrid[0][i] != 1; i++)
1
{
table[i] = 1;
}
for (int i = 1; i < r; i++)
{
//注意:如果是只有单列的时候,每列需要初始化
//注意:不等于1的时候是填回上一列的值,并非初始化为1
if (obstacleGrid[i][0] == 1) table[0] = 0;
for (int j = 1; j < c; j++)
{
if (obstacleGrid[i][j] != 1)
table[j] += ta