如何求组合

Young_UN

2026-06-20 17:59:51

发布于：上海

21阅读

0回复

0点赞

$f1(递归)$

依据：

杨辉三角：
$C(n-1,m-1)左上,C(n-1,m)上$

#include<bits/stdc++.h>
using namespace std;
int C(int n,int m){
    if(m==0||m==n)return 1;
    return C(n-1,m-1)+C(n-1,m);
}
/*
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
*/
int main(){
    cout<<C(4,2)<<endl;
    return 0;
}
//ans: 6

$f2(递推)$

依据：

杨辉三角

#include<bits/stdc++.h>
using namespace std;
int dp[105][105]; 
int C(int n){
    for(int i=0;i<=n;i++){
        for(int j=0;j<=i;j++){
            if(j==0||j==i)dp[i][j]=1;
            else dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
        }
    }
}
/*
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
*/
int main(){
    cout<<C(4,2)<<endl;
    return 0;
}
//ans: 6