EOJ(动态规划）——3005. 小型组合数

单测试点时限: 2.0 秒

内存限制: 256 MB

我们经常需要计算组合数

它表示从 m 个元素中任取 n 个的话，有多少种取法。

例如：从 100 个元素中取 2 个，第一个有 100 种取法，第二个有 99 种取法，再除以两个元素的排列数，共 4950 种取法。

编程计算 m 不大时的组合数值。

输入
第 1 行：整数 T (1≤T≤10) 为问题数

对于每组测试数据：

每行两个整数，m，n,1≤m≤40，0≤n≤m。

输出
对于每个问题，输出一行问题的编号（格式：case #0: 等）。

然后在一行中输出组合数

样例
input
3
2 0
5 3
40 20
output
case #0:
1
case #1:
10
case #2:
137846528820

题目大意：

求小的组合数。

题目解析：

由于范围较小，可以使用杨辉三角打表来做，这种方法最简单。

具体代码：

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 41
long long A[MAXN][MAXN];
void init(){
	for(int i=0;i<MAXN;i++){
		A[i][0]=A[i][i]=1;
	}
	for(int i=2;i<MAXN;i++){
		for(int j=1;j<i;j++){
			A[i][j]=A[i-1][j-1]+A[i-1][j];
		}
	}
}
int main() {
	int T;
	cin>>T;
	init();
	for(int i=0;i<T;i++){
		cout<<"case #"<<i<<":"<<endl;
		int a,b;
		cin>>a>>b;
		cout<<A[a][b]<<endl;
	}
	return 0;
}