leetcode 随笔 Unique Paths & Unique PathsII

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 7 x 3 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Example 1:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2:

Input: m = 7, n = 3
Output: 28

非常简单的问题，即求C(m+n-2,n)的值。

注意数据类型选用long long 否则可能出现越界的情况。

终于写了个超过100%的程序了，哈哈。

class Solution {
public:
    int uniquePaths(int m, int n) {
        long long count1=1,count2=1,hint=m+n-2,l=m>n?n:m;l--;
        while(l) {count1*=(hint);count2*=l;hint--;l--;}
        return count1/count2;
    }
};

很开心。

++++++++++++++++++++++++++++++++++++++++++++++++++++

++++++++++++++++++++++++++++++++++++++++++++++++++++

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.

Note: m and n will be at most 100.

Example 1:

Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

这次跟上次比多了一些“障碍”，也就是矩阵中的1，是不能走的，这个题就没办法取巧了，只能老老实实动态规划。

动态规划是记录一个矩阵，矩阵的每个元素表示它到最后一点位置的路径的个数。显然，最后一项是1，

最后一项的上面一项如果可以走，那么也是1，左边那项可以走也是1。

除了边上，能走我就是下面一项和右边一项的和，最好相当于遍历一遍矩阵得到第一项的路径个数。

时间复杂度log(m*n) 下面代码runtime是4ms，超过99%还是很爽的。

不过刚开始用递归居然跑了200多ms，都超出了显示范围了！哈哈

class Solution {
public:
	int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
		int n = obstacleGrid.size() - 1, m = obstacleGrid[n].size() - 1;
		if (obstacleGrid[0][0] == 1 || obstacleGrid[n][m] == 1) return 0;
		int **record = new int*[n+1];
		for (int i = 0; i < n+1; i++)
		{
			record[i] = new int[m+1];
			memset(record[i], 0, sizeof(int)*(m+1));
		}
        record[n][m]=1;
		for (int i = n-1; i >= 0; i--)
		{
			if (!obstacleGrid[i][m])
			{
				record[i][m] = record[i + 1][m];
			}
			else record[i][m] = 0;
		}
		for (int i = m - 1; i >= 0; i--)
		{
			if (!obstacleGrid[n][i])
			{
				record[n][i] = record[n][i+1];
			}
			else record[n][i] = 0;
		}
		for (int i = n - 1; i >= 0; i--)
		{
			for (int j = m - 1; j >= 0; j--)
			{
				if (!obstacleGrid[i][j])
				{
					record[i][j] = record[i][j + 1]+record[i+1][j];
				}
				else record[i][j] = 0;
			}
		}
		return record[0][0];
	}
};