组合数（杨辉三角递推）

这个求法其实是组合数的来源

伟大的古代劳动人民智慧的结晶

杨辉三角

大家可以观察这个杨辉三角

$$1$$

$$1\ 1$$

$$1\ 2\ 1$$

$$1\ 3\ 3\ 1$$

$$1\ 4\ 6\ 4\ 1$$

$$1\ 5\ 10\ 10\ 5\ 1$$

$$1\ 6\ 15\ 20\ 15\ 6\ 1$$

三角形的左右两条腰上的数组均为1，并且任意一位数等于其左上与右上的两个数字之和

我们就可以得到递推公式

$$ combinations[i][j] = combinations[i - 1][j - 1] + combinations[i - 1][j] $$

以下就是组合数的递推求法的模板

递推求法的码量相对较小，但是针对较大数据的求值并不友好，时空复杂度较大

/*
 * @Author: Gehrychiang
 * @Date: 2020-01-22 15:02:57
 * @Website: www.yilantingfeng.site
 * @E-mail: gehrychiang@aliyun.com
 */
#include <bits/stdc++.h>
using namespace std;
long long combinations[67][67];
const int MAXN = 65;
void cal()
{
    for (int i = 0; i <= MAXN; i++)
    {
        combinations[i][0] = 1;
        combinations[i][i] = 1;
        for (int j = 1; j < i; j++)
        {
            combinations[i][j] = combinations[i - 1][j - 1] + combinations[i - 1][j];
            //如需取模在此操作
        }
    }
}
int main()
{
    cal();
    int n, m;
    while (cin >> n >> m)
    {
        cout << combinations[n][m] << endl;
    }
    return 0;
}