点击获取原题链接
计算组合数 Time Limit: 1000MS Memory Limit: 32768KB Problem Description
计算组合数。C(n,m),表示从n个数中选择m个的组合数。 计算公式如下： 若：m=0，C(n,m)=1 否则， 若 n=1，C(n,m)=1 否则，若m=n，C(n,m)=1 否则 C(n,m) = C(n-1,m-1) + C(n-1,m).
Input
第一行是正整数N，表示有N组要求的组合数。接下来N行，每行两个整数n，m (0 <= m <= n <= 20)。 Output 输出N行。每行输出一个整数表示C(n,m)。 Example Input
3 2 1 3 2 4 0
Example Output
2 3 1
Hint
Author
/*记忆化搜索**/
#include <bits/stdc++.h> using namespace std; int a[25][25]= {0};///记忆化搜索 long long f(int n,int m)///记忆化核心思想用一个数组来存放已经就算出来的数据避免反复计算 { if(m==0 || n==1 || m==n) { a[m][n]=1; return 1; } else { if(a[n][m]) { return a[n][m]; } else { a[n][m] = f(n-1,m-1) + f(n-1,m); return f(n-1,m-1) + f(n-1,m); } } } int main() { int T; cin>>T; while(T--) { int n,m; cin>>n>>m; cout<<f(n,m)<<endl;///递归调用 } return 0; } /*************************************************** User name: Result: Accepted Take time: 0ms Take Memory: 164KB Submit time: 2017-03-08 19:24:59 ****************************************************/