LeetCode Unique 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 as1and0respectively 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 is2.

Note:mandnwill be at most 100.

和Unique PathsI差不多，不过增加了一个判断条件，如果有障碍的话，那么这个格就填写0，表示0个路径。

不过做这道题还是有点麻烦的：

1 需要初始化动态规划法表的第一行

2 每次需要更新表的第一个格

不过也可以简单点，如果使用额外的一个存储空间，可以少一个判断条件。LeetCode上有程序是这么写的。

不过我这里是不使用额外空间，增加一个判断（程序中注意的地方）就可以了，从简洁度来说，好像也差不多。看各人喜欢了。

class Solution {
public:
	//头脑考虑问题不够全面就会有bug，需要严谨的逻辑思维
	int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
		int r = obstacleGrid.size();
		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++)
		{
			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] += table[j-1];
				else table[j] = 0;
			}
		}
		return table[c-1];
	}
};

//2014-2-7 update
	int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) 
	{
		if (obstacleGrid.empty() || obstacleGrid[0].empty()) return 0;

		int *A = new int[obstacleGrid[0].size()];
		if (!obstacleGrid[0][0]) A[0] = 1;
		else return 0;

		for (int i = 1; i < obstacleGrid[0].size(); i++)
		{
			if (obstacleGrid[0][i]) A[i] = 0;
			else A[i] = A[i-1];
		}

		for (int i = 1; i < obstacleGrid.size(); i++)
		{
			if (obstacleGrid[i][0]) A[0] = 0;
			for (int j = 1; j < obstacleGrid[0].size(); j++)
			{
				if (obstacleGrid[i][j]) A[j] = 0;//经常写错下标
				else A[j] += A[j-1];
			}
		}
		return A[obstacleGrid[0].size()-1];
	}

//2014-2-7 update
	int uniquePathsWithObstacles2(vector<vector<int> > &obstacleGrid) 
	{
		if (obstacleGrid.empty() || obstacleGrid[0].empty()) return 0;
		int *A = new int[obstacleGrid[0].size()+1];
		A[0] = 0;
		if (obstacleGrid[0][0]) return 0;
		else A[1] = 1;
		for (int i = 1; i < obstacleGrid[0].size(); i++)
		{
			if (obstacleGrid[0][i]) A[i+1] = 0;
			else A[i+1] = A[i];
		}

		for (int i = 1; i < obstacleGrid.size(); i++)
		{
			for (int j = 0; j < obstacleGrid[0].size(); j++)
			{
				if (obstacleGrid[i][j]) A[j+1] = 0;
				else A[j+1] += A[j];
			}
		}
		return A[obstacleGrid[0].size()];//经常没写return
	}