整数划分问题解法2动态规划

整数划分 &＃xff0d;&＃xff0d;&＃xff0d; 一个老生长谈的问题:
　　1) 练练组合数学能力.
　　2) 练练递归思想
　　3) 练练DP
　　总之是一道经典的不能再经典的题目:
　　这道好题求:
　　1. 将n划分成若干正整数之和的划分数。
　　2. 将n划分成k个正整数之和的划分数。
　　3. 将n划分成最大数不超过k的划分数。
　　4. 将n划分成若干奇正整数之和的划分数。
　　5. 将n划分成若干不同整数之和的划分数。

1.将n划分成不大于m的划分法&＃xff1a; 

 　　1).若是划分多个整数可以存在相同的&＃xff1a;

 　　 dp[n][m]&＃61; dp[n][m-1]&＃43; dp[n-m][m]  dp[n][m]表示整数 n 的划分中&＃xff0c;每个数不大于 m 的划分数。
     　　则划分数可以分为两种情况:
     　　a.划分中每个数都小于 m&＃xff0c;相当于每个数不大于 m- 1, 故划分数为 dp[n][m-1].
    　　 b.划分中有一个数为 m. 那就在 n中减去 m ,剩下的就相当于把 n-m 进行划分&＃xff0c; 故划分数为 dp[n-m][m];

　　2).若是划分多个不同的整数&＃xff1a;

　　dp[n][m]&＃61; dp[n][m-1]&＃43; dp[n-m][m-1]   dp[n][m]表示整数 n 的划分中&＃xff0c;每个数不大于 m 的划分数。
   　　 同样划分情况分为两种情况&＃xff1a;
    　　a.划分中每个数都小于m,相当于每个数不大于 m-1,划分数为 dp[n][m-1].
    　　b.划分中有一个数为 m.在n中减去m,剩下相当对n-m进行划分&＃xff0c;

　　　并且每一个数不大于m-1&＃xff0c;故划分数为 dp[n-m][m-1]

2.将n划分成k个数的划分法&＃xff1a;

　dp[n][k]&＃61; dp[n-k][k]&＃43; dp[n-1][k-1];

   　　方法可以分为两类&＃xff1a;
   　　　　第一类: n 份中不包含 1 的分法&＃xff0c;为保证每份都 >&＃61; 2&＃xff0c;可以先拿出 k 个 1 分
   　　到每一份&＃xff0c;然后再把剩下的 n- k 分成 k 份即可&＃xff0c;分法有: dp[n-k][k]
  　　 　　第二类: n 份中至少有一份为 1 的分法&＃xff0c;可以先那出一个 1 作为单独的1份&＃xff0c;剩
   　　下的 n- 1 再分成 k- 1 份即可&＃xff0c;分法有&＃xff1a;dp[n-1][k-1]

3.将n划分成若干奇数的划分法&＃xff1a;

　　　　g[i][j]:将i划分为j个偶数

　　　　f[i][j]:将i划分为j个奇数
　　   g[i][j] &＃61; f[i - j][j];
   　　f[i][j] &＃61; f[i - 1][j - 1] &＃43; g[i - j][j];

 方法可以分为两类&＃xff1a;

  第一类&＃xff1a;i中拿出j个1分到每一份中&＃xff0c;将剩余的i-j分成j个奇数

  第二类&＃xff1a;一份包含奇数1&＃xff0c;剩余的i-1分成j-1个奇数&＃xff1b;另一种&＃xff0c;每份至少大于1&＃xff0c;将j个1拿出来分到每一份中&＃xff0c;其余i-j分成j份

　　代码如下所示&＃xff08;转载&＃xff09;&＃xff1a;

/** hit1402.c** Created on: 2011-10-11* Author: bjfuwangzhu*/#include
#include<string.h>
#define nmax 51
int num[nmax][nmax]; //将i划分为不大于j的个数
int num1[nmax][nmax]; //将i划分为不大于j的不同的数
int num2[nmax][nmax]; //将i划分为j个数
int f[nmax][nmax]; //将i划分为j个奇数
int g[nmax][nmax]; //将i划分为j个偶数
void init() {int i, j;for (i &＃61; 0; i 0] &＃61; 0, num[0][i] &＃61; 0, num1[i][0] &＃61; 0, num1[0][i] &＃61; 0, num2[i][0] &＃61;0, num2[0][i] &＃61; 0;}for (i &＃61; 1; i for (j &＃61; 1; j if (i 0;} else if (i &＃61;&＃61; j) {num[i][j] &＃61; num[i][j - 1] &＃43; 1;num1[i][j] &＃61; num1[i][j - 1] &＃43; 1;num2[i][j] &＃61; 1;} else {num[i][j] &＃61; num[i][j - 1] &＃43; num[i - j][j];num1[i][j] &＃61; num1[i][j - 1] &＃43; num1[i - j][j - 1];num2[i][j] &＃61; num2[i - 1][j - 1] &＃43; num2[i - j][j];}}}f[0][0] &＃61; 1, g[0][0] &＃61; 1;for (i &＃61; 1; i for (j &＃61; 1; j <&＃61; i; j&＃43;&＃43;) {g[i][j] &＃61; f[i - j][j];f[i][j] &＃61; f[i - 1][j - 1] &＃43; g[i - j][j];}}
}
int main() {
#ifndef ONLINE_JUDGEfreopen("data.in", "r", stdin);
#endifint n, k, i, res0, res1, res2, res3, res4;init();while (~scanf("%d %d", &n, &k)) {res0 &＃61; num[n][n];res1 &＃61; num2[n][k];res2 &＃61; num[n][k];for (i &＃61; 0, res3 &＃61; 0; i <&＃61; n; i&＃43;&＃43;) {res3 &＃43;&＃61; f[n][i];}res4 &＃61; num1[n][n];printf("%d\n%d\n%d\n%d\n%d\n\n", res0, res1, res2, res3, res4);}return 0;
}