codevs 1039 数的划分

题目描述   Description                   

将整数n分成k份，且每份不能为空，任意两种划分方案不能相同(不考虑顺序)。问有多少种不同的分法。

例如：n=7，k=3，下面三种划分方案被认为是相同的。

1 1 5

1 5 1

5 1 1

输入描述   Input Description              

输入：n，k (6<n<=200，2<=k<=6)

输出描述  

Output Description              

输出：一个整数，即不同的分法。

样例输入  

Sample Input              

 7 3

样例输出  

Sample Output              

4

 

思路——划分型dp

f[i][j]是指将i划分成j部分的方案数

初始化f[0][0]=1

f[i][j]有意义（i>=j）的情况下满足公式 f[i][j]=f[i-1][j-1]+f[i-j][j]

 

解释：

分为两种情况 一种情况分出来的数中含1 另一种情况分出来的数中不含1

以下均以i分为j组举例

情况1：分离出一个1，那么剩余的i-1就只能划分成j-1个部分

情况2：不包含1    为了不包含1把最终所划分的j组每组都放上一个1，由于不能划分出0，因此不论剩下的数怎么划分，j组中都不可能有1.即将剩下的i-j分为j组

 

1 #include
        
          2 #include
         
           3 #include
          
            4 #include
           
             5 #include
            
              6 #include
             
               7 8 using namespace std; 9 10 int n,m,dp[210][7];11 int main()12 {13 scanf("%d%d",&n,&m);14 dp[0][0]=1;15 for(int i=1;i<=n;i++)16 {17 for(int j=1;j<=m;j++)18 {19 if(i>=j)dp[i][j]=dp[i-1][j-1]+dp[i-j][j];20 }21 }22 printf("%d",dp[n][m]);23 system("pause");24 return 0;25 }