100000015 - lattice paths

如果只允许向下和向右走，则在2×2的方格的左上角顶点沿着方格边线走到右下角，只有6中可能。

那么，方格变为20×20的时候，共有多少种移动路径？

n。

测试点一：n=20。

测试点二：n=25。

a、众所周知，这个问题是非常简单的DP、记忆化搜索。

b、如果你已经通过了，那么思考这样一个问题：

在2×2的方格上任意一条路径，经过几段“短边”达到终点？

在20×20的放个上呢？

很简单是吧，只有x,y方向都走20才能达到终点，而无论路径是什么样的。

于是，可以从排列组合的角度来解决：共有40步，40步中每一步都有两种选择方式，即C(40,20)。

但是，组合数的解法并没有到此为止，你要知道组合数求解存在溢出问题，思考如何利用组合数分子一定能整除分母的特性，编写恰当的代码使得计算过程中不会溢出。