NYOJ-571 整数划分(三)

此题是个非常经典的题目，这个题目包含了整数划分(一)和整数划分(二)的所有情形，而且还增加了其它的情形，主要是用递归或者说是递推式来解，只要找到了递推式剩下的任务就是找边界条件了，我觉得边界也是非常重要的一步，如果找不准边界，这个题也很难做出来，当时我就是找边界找了好长时间，边界得琢磨琢磨。递推步骤如下：

第一行:将n划分成若干正整数之和的划分数。
状态转移方程：dp[i][j]:和为i、最大数不超过j的拆分数
dp[i][j]可以分为两种情况：1、拆分项至少有一个j 2、拆分项一个j也没有
dp[i][j] = dp[i-j][[j] + dp[i][j-1]

第二行：将n划分成k个正整数之和的划分数。
dp[n-k][k]：相当于把k个1从n中拿出来，然后和n-k的拆分项相加的个数

第三行：将n划分成若干最大不超过k的正整数之和的划分数。
dp[n][k]

第四行：将n划分成若干奇正整数之和的划分数。
dp1[i][j]是当前的划分数为i,最大值为j时的中的划分数，则状态转移方程为
if(i < j && j % 2 == 1)
dp1[i][j] = dp1[i][i]
if(i < j && j % 2 == 0) (最大数不可能为偶数)
dp1[i][j] = dp1[i][i-1]
划分数中有j时的划分为dp[i][j - 2]，因为它是奇数，所以要减2，
如果划分数中没有j的时候， 则它的数目可以写成dp1[i-j][j];意思就是i去掉j后，然后再划分最大为j的
即dp1[i][j] = dp1[i-j][j] + dp1[i][j-2]

第五行：将n划分成若干完全不同正整数之和的划分数。
dp2[i][j]可以分两种情况：1、dp1[i][j-1]为不选择j时的方案 2、dp1[i-j][j-1]为选择j时的方案
0-1背包：dp2[i][j] = dp2[i][j-1] + dp2[i-j][j-1]

方法一(递归法)：

 #include <stdio.h>

 //less_m(n, m)表示将n划分为最大是m的数

 int less_m(int n, int m)

 {

     if(n ==  || m == )

         return ;

     if(n < m)

         return less_m(n, n);

     else if(n == m)

         return  + less_m(n, m - );

     else

         return less_m(n, m - ) + less_m(n - m, m);

 }

 //count(n, m)表示将n划分为m个数

 int count(int n, int m)

 {

     if(n < m)

         return ;

     if(m ==  || n == m)

         return ;

     else

         return count(n - , m - ) + count(n - m, m);

 }

 //odd(n, m)表示将n划分为最大数为m的奇数之和

 int odd(int n, int m)

 {

     if(m == )

         return ;

     if(n ==  && m %  == )

         return ;

     if(n ==  && m == )

         return ;

     if(n < m)

     {

         if(n %  == )

             return odd(n, n - );

         else

             return odd(n, n);

     }

     else

     {

         return odd(n - m, m) + odd(n, m - );

     }

 }

 //not_duplicate(n, m)是将n划分为最大为m的数， 并且没有重复的

 int not_duplicate(int n, int m)

 {

     if(m == )

         return ;

     if(n ==  || n == )

         return ;

     if(n < m)

         return not_duplicate(n, n);

     else

         return not_duplicate(n, m - ) + not_duplicate(n - m, m - );

 }

 int main()

 {

     int n, k;

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

     {

         printf("%d\n", less_m(n, n));

         printf("%d\n", count(n, k));

         printf("%d\n", less_m(n, k));

         if(n %  == )

             printf("%d\n", odd(n, n));

         else

             printf("%d\n", odd(n, n - ));

         printf("%d\n\n", not_duplicate(n, n));

     }

     return ;

 }

方法二(递推法dp):

 #include <stdio.h>

 const int MAX = ;

 int dp[MAX][MAX], dp1[MAX][MAX], dp2[MAX][MAX];

 void divide()

 {

     dp[][] = ;

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

     {

         for(int j = ; j < MAX; j++)

         {

             if(i < j)

                 dp[i][j] = dp[i][i];

             else

                 dp[i][j] = dp[i][j - ] + dp[i - j][j];

         }

     }

 }

 //这是划分奇数的函数

 void divide1()

 {

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

         dp1[i][] = ;

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

         dp1[][i] = ;

     dp1[][] = ;

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

     {

         for(int j = ; j < MAX; j += )

         {

             if(i < j)

             {

                 if(i %  == )

                     dp1[i][j] = dp1[i][i];

                 else

                     dp1[i][j] = dp1[i][i - ];

             }

             else

                 dp1[i][j] = dp1[i][j - ] + dp1[i - j][j];

         }

     }

 }

 //划分没有重复数字的函数

 void divide2()

 {

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

         dp2[][i] = dp2[][i] = ;

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

     {

         for(int j = ; j < MAX; j++)

         {

             if(i < j)

                 dp2[i][j] = dp2[i][i];

             else

                 dp2[i][j] = dp2[i][j - ] + dp2[i - j][j - ];

         }

     }

 }

 int main()

 {

     int n, k;

     divide();

     divide1();

     divide2();

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

     {

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

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

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

         //先要判断要划分的数是否是奇数

         printf("%d\n", (n & ) ? dp1[n][n] : dp1[n][n - ]);

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

     }

 }

NYOJ-571 整数划分(三)的相关教程结束。