题意：在20×20方阵中从起点出发只允许向右或向下移动到达终点的路径有多少条。
思路：每次只能向右或者向下，总共 40 步，也就是 40 步中每一步都有两种选择，也就是 C (40 , 20) 。
为什么能在计算分子的时候不断约分掉分母？首先，组合数是整数，也就是说到最后分子一定能整除分母。我们使用 m 记录当前还没有被约分掉的最大的数，如果分子能够整除掉 m 就进行约分并且 m 更新为下一个等待约分的值。这样做就可以避免在计算组合数中导致的数据溢出问题！
/*************************************************************************
> File Name: euler015.c
> Author: WArobot
> Blog: http://www.cnblogs.com/WArobot/
> Created Time: 2017年06月27日 星期二 20时05分45秒
************************************************************************/
#include <stdio.h>
#include <inttypes.h>
int32_t main() {
int64_t ans = 1 , m = 20;
for (int32_t i = 40 ; i > 20 ; i--) { // 在计算过程中不断约分防止数据溢出
ans *= i;
while (ans % m == 0 && m != 1) {
ans /= m;
--m;
}
}
printf("%"PRId64"
",ans);
return 0;
}
方法二：DP
/*************************************************************************
> File Name: test.cpp
> Author:
> Mail:
> Created Time: 2018年02月03日 星期六 08时42分28秒
************************************************************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[21][21];
int main() {
for (int i = 0 ; i <= 20 ; ++i) {
for (int j = 0 ; j <= 20 ; ++j) {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] += dp[i - 1][j] + dp[i][j - 1];
}
}
}
printf("%lld
", dp[20][20]);
return 0;
}