How do you add?（递推）

时间：2022-02-28 09:12:40

题意：求将n分为k个数相加的种数。

如：n=20，k=2，则可分为：

0+20=20

1+19=20

2+18=20

.......

20 +0=20

共21种方案。

解析：令f（n，m）表示将n分为m个数相加的种数，则 f（n，m）=  ∑ f（n-i，m-1）   （0 ≤ i ≤n）

代码如下：

 # include<iostream>

 # include<cstdio>

 # include<set>

 # include<cstring>

 # include<algorithm>

 using namespace std;

 const int mod=;

 int a[][];///a[i][j]表示把i分为j个数的方法个数；

 int main()

 {

     int i,j,l,n,k;

     memset(a,,sizeof(a));

     for(i=;i<=;++i)

         a[i][]=a[][i]=;

     for(i=;i<=;++i){

         for(k=;k<=;++k){

             for(l=;l<=i;++l){

                 a[i][k]+=a[i-l][k-];

                 a[i][k]%=mod;

             }

         }

     }

     while(scanf("%d%d",&n,&k),n+k)

     {

         printf("%d\n",a[n][k]);

     }

     return ;

 }

这道题和 UVA-12304 Race 如出一辙

或是http://www.cnblogs.com/20143605--pcx/p/4677157.html

相关文章