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 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
思路：
这题很简单，一看就是组合数C(n,m)=C(n-1,m)+C(n-1,m-1)或者跟Unique Paths II中P(i,j)=P(i-1,j)+P(i,j-1)一样递归求解OK
但是，如果考虑m和n再大一些的情况应该怎么办呢，递归会tle吧，直接求解下式看看
1. long long直接计算三个阶乘分分钟hold不住溢出啊，过1,100的时候就已经Runtime Error了。
2. 为了避免直接计算n的阶乘，对公式两边取对数，于是得到：C(m+n,m) = exp(ln(C(m+n,m))) = exp(ln((m+n)!) - ln(m!) - ln(n!))
(还可以进一步消去重叠的部分)，算法时间复杂度仍然是 O( m )，虽然浮点计算比整数计算要慢。
不过引入浮点数计算，最终的结果可能不一定是精确的，m和n一大估计也过不了OJ
int uniquePaths(int m, int n) {
double prod = , pm, pn;
for(int i = ; i <= m+n-; i++){
prod += log(i);
if(i == m-) pm = prod;
if(i == n-) pn = prod;
}
return static_cast<int>(exp(prod-pm-pn)+0.5);//(int)exp(prod-pm-pn)误差大，过不了所有test case
}
3. ACM界还有种素数化简+取模的方法，n! = 2^p[i] * 3^p[i] * 5^p[i]*......
这用到的是哥德巴赫猜想：
1.任何一个实数都可以写成几个素数的和（1+1=2）
2.任何一个实数都可以写成几个素数的积（3！=3x2,6!=２＾４＊３＾２＊５＾１）底数都是素数
3.a*b%c=(a%c)*(b%c)
这样我们就可以将C（n,m）分解为素数相乘的模式，如：C（6,3）=（２＾４＊３＾２＊５＾１）/((3x2)*(3x2));
下面涉及到两个问题：
1. 素数打表：筛选法
筛出2~n 范围里的所有素数。
1)将所有候选数2~n放入筛中;
2)找出筛中最小数P
3)宣布P为素数，并将P的所有倍数从筛中筛去;
4)重复2)至3)直到筛空.
其实，当P>sqrt(n)时筛中剩下的数就已经都是素数了。
2. 分解实数(求素数指数)
可以筛出
2~n
范围里的所有素数。
1)
将所有候选数
2~n
放入筛中
;
2)
找出筛中最小数
P
，
P
一定为素数。
3)
宣布
P
为素数，并将
P
的所有倍数从筛中筛去
;
4)
重复
2)
至
3)
直到筛空
.
其实，当
P>sqrt(n)
时筛中剩下的数就已经都是素数了。