【题解】【排列组合】【素数】【Leetcode】Unique Paths

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?

【题解】【排列组合】【素数】【Leetcode】Unique Paths

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吧,直接求解下式看看

【题解】【排列组合】【素数】【Leetcode】Unique Paths

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!=2^4*3^2*5^1)底数都是素数
3.a*b%c=(a%c)*(b%c)

这样我们就可以将C(n,m)分解为素数相乘的模式,如:C(6,3)=(2^4*3^2*5^1)/((3x2)*(3x2));

下面涉及到两个问题:

1. 素数打表:筛选法

筛出2~n 范围里的所有素数。

1)将所有候选数2~n放入筛中;

2)找出筛中最小数P

3)宣布P为素数,并将P的所有倍数从筛中筛去;

4)重复2)至3)直到筛空.

其实,当P>sqrt(n)时筛中剩下的数就已经都是素数了。

2. 分解实数(求素数指数)

详见:组合数的素数算法(ACM基础教程1010)

可以筛出

2~n

范围里的所有素数。

1)

将所有候选数

2~n

放入筛中

;

2)

找出筛中最小数

P

P

一定为素数。

3)

宣布

P

为素数,并将

P

的所有倍数从筛中筛去

;

4)

重复

2)

3)

直到筛空

.

其实,当

P>sqrt(n)

时筛中剩下的数就已经都是素数了。

上一篇:【题解】【矩阵】【回溯】【Leetcode】Unique Paths II


下一篇:【leetcode】 Unique Binary Search Trees (middle)☆