组合数C(n,m)=C(n-1,m)+C(n-1,m-1) 即对于第n个,不选和选
组合数代码实现:(n>20时)
(方法2的证明,拍的歪了emmm)
//方法1:O(n^2)
int ans[maxn][maxn];
int n=5,m=3;
for(int i=1;i<=5;i++)
ans[i][i]=ans[i][0]=1;//i个里面选i个和i个里面选0个
for(int i=2;i<=n;i++)
for(int j=1;j<=i/2;j++)
{
ans[i][j]=ans[i-1][j]+ans[i-1][j-1];
ans[i][i-j]=ans[i][j];//避免再重复计算,直接赋值
}
cout<<ans[5][3]<<endl;
//方法2:O(m)
long long res=1;
for(int i=1;i<=m;i++)
res=res*(n-m+i)/i;
cout<<res<<endl;
//两个输出结果都是10
-
n*m大小的棋盘,每次都只能向下或者向右走一步,求从左上角到右下角共有多少条路
dp方法: dp[i][j]=dp[i-1][j]+dp[i][j-1];
组合数方法:从左上角到右下角一共要走m+n-2步,这些步数里面有n-1个向下的步数,m-1个向右的步数
方法数:C(m+n-2,n-1) or C(m+n-2,m-1)
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
int dp[10][10]={0};
int n=2,m=2;
//dp
dp[1][1]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!(i==1&&j==1))
dp[i][j]=dp[i-1][j]+dp[i][j-1];
//组合数
int ans1=1;
for(int x=n;x<=m+n-2;x++)
ans1*=x;
int ans2=1;
for(int x=1;x<=m-1;x++)
ans2*=x;
cout<<dp[n][m]<<endl;
cout<<ans1/ans2;
return 0;
}
-
n*m大小的棋盘,每次都只能向下或者向右走一步,且不经过点P,求从右下角到左上角共有多少条路
如图:
用组合数学的方法做:A->B-(A->P)*(P->B) 即c(12,5)-(c(6,3)*c(6,2)) 结果为A
如果也不能经过C,C在P的左下方且和P重合,方法数:A->B-(A->P)*(P->B)-(A->C)*(C->B)+(A->C)*(C->P)*(P->B)
-
(稍微复杂一点) 寻宝路径那道题,路径的求取受到条件限制
详情:https://blog.csdn.net/Cassie_zkq/article/details/88344158