本博文源于胡凡的《算法笔记》，旨在用三种方法实现组合数计算。
方法一：通过定义式直接计算
先计算n!,然后令其分别处以m!和(n-m)!即可。这种方法计算量庞大，至少n!数量级时间复杂度
ll C(ll n,ll m){
ll ans = 1;
for(ll i = 1;i<= n;i++){
ans *= i;
}
for(ll i = 1;i <= m;i++){
ans/=i;
}
for(ll i = 1;i<= n-m;i++) {
ans /= i;
}
return ans;
}
方法二：通过递推公式计算
利用公式
C
n
m
=
C
n
−
1
m
+
C
n
−
1
m
−
1
C_n^m = C_{n-1}^m+C_{n-1}^{m-1}
Cnm=Cn−1m+Cn−1m−1
ll C(ll n,ll m){
if(m==0 || m == n) return 1;
return C(n-1,m)+C(n-1,m-1);
}
方法三：结果赋值给数组
用数组存储在之前重复计算的数字，然后就不用重复计算。
ll res[67][67]={0};
ll C(ll n,ll m){
if(m==0 || m==n) return 1;
if(res[n][m] != 0)return res[n][m];
return res[n][m] = C(n-1,m)+ C(n-1,m-1);//赋值给res[n][m]并返回
}
完整源码
#include<iostream>
using namespace std;
//方法1 通过定义式直接计算
typedef long long ll;
ll res[67][67]={0};
ll C(ll n,ll m){
if(m==0 || m==n) return 1;
if(res[n][m] != 0)return res[n][m];
return res[n][m] = C(n-1,m)+ C(n-1,m-1);//赋值给res[n][m]并返回
}
int main()
{
printf("%ld",C(6,3));
return 0;
}