LeetCode Unique Paths

Unique Paths

A robot is located at the top-left corner of amxngrid (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 3 x 7 grid. How many possible unique paths are there?

Note:mandnwill be at most 100.

这里Note：的含义是如果数值过大会溢出的。

这道题对我来说是很新颖的了，因为我之前没见过。但是其实解法却是非常老套的，我一开始居然没想到，所以总结了一下：

方法论总结：
遇上新颖没见过的题目：
1） 查看其特征；

2） 搜索大脑有什么熟悉的题目，可以套的，或者相似的可以退到出来的；

3） 罗列出来这些题目：全排列， 水槽，TwoSum，等等；

4） 搜索大脑里面有什么熟悉的算法；

5） 罗列出来：动态规划法，递归，回溯，二叉树遍历，贪心法，递归树，分治法，观察特征计算法，等等，肯定有可以套的算法的！

6）最后选定算法解题；

7）没有优化的算法，可以使用暴力法，先解决再说！

去掉无用信息，错误解法，一定要把头脑中的一团乱麻理清，整理出逻辑来！
最后实在没招了，想办法让人提示，主要是提示用什么算法，能给个思路更好了，O(∩_∩)O~

在leetcode论坛上的找了提示，一下子就很多思路了。而且写出的程序也很简单。

这道题是属于思想难，但是程序容易的题目。

http://discuss.leetcode.com/questions/85/unique-paths

下面是经验证结果是正确的回溯法，但是超时。

Leetcode上的有回溯法程序需要5行代码，其实不用，我这里只需要2行，O(∩_∩)O~

int uniquePathsBackTrack(int m, int n) {
		if(m==1 || n==1) return 1;
		return uniquePaths(m-1, n) + uniquePaths(m, n-1);
	}

动态规划法：

int uniquePaths(int m, int n) 
	{
		vector<vector<int> > table(m, vector<int>(n, 1));
		for (int i = 1; i < m; i++)
		{
			for (int j = 1; j < n; j++)
			{
				table[i][j] = table[i-1][j] + table[i][j-1];
			}
		}
		return table[m-1][n-1];
	}

省内存的动态规划法：

//Save space
	int uniquePaths2(int m, int n)
	{
		vector<int> table(n, 1);
		for (int i = 1; i < m; i++)
		{
			for (int j = 1; j < n; j++)
			{
				table[j] += table[j-1];
			}
		}
		return table[n-1];
	}

可以进一步提高一点时间效率：

//Improve efficency further
	int uniquePaths3(int m, int n)
	{
		int a = min(m,n);
		int b = max(m,n);
		vector<int> table(b, 1);
		for (int i = 1; i < a; i++)
		{
			table[i] *= 2; //n<m的时候会出错，所以要用ab处理一下
			for (int j = i + 1; j < b; j++)
			{
				table[j] += table[j-1];
			}
		}
		return table[b-1];
	}

//2014-2-2 update
	int uniquePaths(int m, int n)
	{
		if (n == 1 || m == 1) return 1;

		int *A = new int[n];
		for (int i = 1; i <= n; i++)
		{
			A[i-1] = i;//i-1写出i会造成下标超范围
		}

		for (int i = 2; i < m; i++)
		{
			for (int j = 1; j < n; j++)
			{
				A[j] += A[j-1];
			}
		}
		return A[n-1];
	}