学步园

          整数的划分问题是一个很经典的问题，它的变形也非常的多，总结了一下，大概有以下几种变形：

1) 将 N 划分为若干个正整数的和的划分数

2) 将 N 划分为若干个不同的正整数的和的划分数

3) 将 N 划分为不超过K 个正整数的和的划分数

4) 将 N 划分为不超过K 个不同正整数的和的划分数

5) 将 N 划分为最大数不超过K 的正整数的和的划分数

6) 将 N 划分为若干个连续正整数的和的划分数

ohoh，怎么这么多@@

变形(1): 将 N 划分为若干个正整数的和的划分数。比如 6，可以这样划分：

              6
              5 + 1 
              4 + 2, 4 + 1 + 1
              3 + 3, 3 + 2 + 1, 3 + 1 + 1 + 1
              2 + 2 + 2, 2 + 2 + 1 + 1, 2 + 1 + 1 + 1 + 1
              1 + 1 + 1 + 1 + 1 + 1

             所以答案应该是 11.

             分析：

                      根据 n和 m的关系，考虑以下几种情况：

   (1 )当 n=1时，不论 m的值为多少（ m>0)，只有一种划分即 {1};

   (2) 当 m=1时，不论 n的值为多少，只有一种划分即 n个 1， {1,1,1,...,1};

   (3) 当 n=m时，根据划分中是否包含 n，可以分为两种情况：

( a)划分中包含 n的情况，只有一个即 {n}；

( b)划分中不包含 n的情况，这时划分中最大的数字也一定比 n小，即 n的所有 (n-1)划分。

     因此 f(n,n) =1 + f(n,n-1);

   ( 4)当 n<m时，由于划分中不可能出现负数，因此就相当于 f(n,n);

   ( 5)但 n>m时，根据划分中是否包含最大值 m，可以分为两种情况：

( a)划分中包含 m的情况，即 {m, {x1,x2,...xi}}, 其中 {x1,x2,... xi} 的和为 n-m，可能再次出现 m，因此是（ n-m）的 m划分，

     因此这种划分个数为 f(n-m, m);

( b)划分中不包含 m的情况，则划分中所有值都比 m小，即 n的 (m-1)划分，个数为 f(n,m-1);

     因此 f(n, m) = f(n-m, m)+f(n,m-1);

             因此，设dp[n][m] 表示将 n 划分为 最大数不超过 m 的划分个数，有

                              dp[n][m] = 1                                                    ( m = 1)

                              dp[n][m] = dp[n][m-1] + 1                              ( m = n)

                              dp[n][m] = dp[n][n]                                         ( m > n)

                              dp[n][m] = dp[n][m-1] + dp[n-m][m]             ( m < n)

Code:

变形(2):将 N 划分为若干个不同正整数的和的划分数   TOJ.3511  Staircases

             依然是DP，转移方程为 a[k][n]=a[k+1][n]+a[k+1][n-k];其中a[k][n]表示将n划分为不小于k种不同的数的划分法。

                                   初始化为 a[n][n]=1  ; a[k][n]=0 (k>n).

Code：

变形(3):将 N 划分为不超过K 个正整数的和的划分数

            解法：dp[i][j] 表示将 i 划分为 j 份的划分数，则转换为求 sigma( dp[N][ i ] )  (i <= K);

                        dp[i][j] 的转移方程为 dp[i-1][j-1] + dp[i-j][j];

            详细见http://wurong81.spaces.live.com/blog/cns!5EB4A630986C6ECC!254.entry

Code:

变形(4):将 N 划分为不超过K 个不同正整数的和的划分数

          解法：即为变形2的方程意义。a[k][n] 表示将 N 划分为不超过K份不同的数的和的划分数

变形(5):

变形(6): 这个最简单了。N 可以写为连续K(K >= 2)个正整数的和，则K <= sqrt(2*N);

               令 i 从 K 到 2 循环，如果 i 为奇数 且 N %i == 0,则可分解为 i 个数，第一个数为 N/i - i/2;

                                                   如果 i 为偶数 且 N %i == i/2，则可分解为i 个数，第一个数为 (N-1)/i - i/2 + 1;