- 原文地址：http://www.cnblogs.com/wanghetao/archive/2013/11/25/3442192.html
- 描述
-
整数划分是一个经典的问题。请写一个程序,完成以下要求.
- 输入
- 每组输入是两个整数n和k。(1 <= n <= 50, 1 <= k <= n)
- 输出
- 对于输入的 n,k;
第一行： 将n划分成若干正整数之和的划分数。
第二行： 将n划分成k个正整数之和的划分数。
第三行： 将n划分成最大数不超过k的划分数。
第四行： 将n划分成若干个 奇正整数之和的划分数。
第五行： 将n划分成若干不同整数之和的划分数。
第六行： 打印一个空行 - 样例输入
-
5 2
- 样例输出
-
7 2 3 3 3
- 提示
- 样例输出提示:
1.将5划分成若干正整数之和的划分为： 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1
2.将5划分成2个正整数之和的划分为： 3+2, 4+1
3.将5划分成最大数不超过2的划分为： 1+1+1+1+1, 1+1+1+2, 1+2+2
4.将5划分成若干 奇正整数之和的划分为： 5, 1+1+3, 1+1+1+1+1
5.将5划分成若干不同整数之和的划分为： 5, 1+4, 2+3
本题使用动态规划（Dynamic Programming）方法解决
一 求将n划分为若干正整数之和的划分数
1. 若划分的多个整数可以相同
设dp[i][j]为将i划分为不大于j的划分数
(1) 当i<j 时，i不能划分为大于i的数，所以dp[i][j]=dp[i][i]；
(2) 当i>j 时，可以根据划分中是否含有j分为两种情况。若划分中含有j，划分方案数为dp[i-j][j]；若划分数中不含j，相当于将i划分为不大于j-1的划分数，为dp[i][j-1]。所以当i>j时dp[i][j]=dp[i-j][j]+dp[i][j-1]；
(3) 当i=j 时，若划分中含有j只有一种情况，若划分中不含j相当于将i划分为不大于j-1的划分数。此时dp[i][j]=1+dp[i][j-1]。
dp[n][n]可以解决问题1，dp[n][k]表示将n划分为最大数不超过k的划分数，可以解决问题3。
2. 若划分的正整数必须不同
设dp[i][j]为将i划分为不超过j的不同整数的划分数
(1) 当i<j时，i不能划分为大于i的数，所以dp[i][j]=dp[i][i]；
(2) 当i>j时，可以根据划分中是否含有j分为两种情况。若划分中含有j，则其余的划分中最大只能是j-1，方案数为dp[i-j][j-1]；若划分中不含j，相当于将i划分为不大于j-1的划分数，为dp[i][j-1]。所以当i>j时dp[i][j]=dp[i-j][j-1]+dp[i][j-1]；
(3) 当i=j时，若划分中含有j只有一种情况，若划分中不含j相当于将i划分为不大于j-1的划分数。此时dp[i][j]=1+dp[i][j-1]
dp[n][n]表示将n划分为不同整数的划分数，可以解决问题5.
二.将n划分为k个整数的划分数
设dp[i][j]为将i划分为j个整数的划分数。
(1) i<j为不可能出现的情况，dp[i][j]=0；
(2) 若i=j，有一种情况：i可以划分为i个1之和，dp[i][j]=1；
(3) 若i>j，可以根据划分数中是否含有1分为两类：若划分数中含有1，可以使用“截边法”将j个划分分别截去一个1，把问题转化为i-j的j-1个划分数，为dp[i-j][j-1]； 若划分中不包含1，使用“截边法”将j个划分数的最下面一个数截去，将为题转化为求i-j的j个划分数，为dp[i-j][j]。所以i>j时dp[i][j]=dp[i-j][j-1]+dp[i-j][j]。
dp[n][k]为将n划分为k个整数的划分数，可解决问题2。
三.将n划分为若干正奇数之和的划分数
设f[i][j]为将i划分为j个奇数之和的划分数，g[i][j]为将i划分为j个偶数之和的划分数。
使用截边法，将g[i][j]的j个划分都去掉1，可以得到f[i-j][j]，所以g[i][j] = f[i-j][j]。
f[i][j]中有包含1的划分方案和不包含1的划分方案。对于包含1的划分方案，可以将1的划分除去，转化为“将i-1划分为j-1个奇数之和的划分数”，即f[i-1][j-1]；对于不包含1的划分方案，可以使用截边法对j个划分每一个都去掉一个1，转化为“将i-j划分为j个偶数之和的划分数”，即g[i-j][j]。
所以f[i][j]=f[i-1][j-1]+g[i-j][j]。
f[n][0]+f[n][1]+……+f[n][n]为将n划分为若干奇数的划分数，为问题4的答案。
参考: [1] http://blog.csdn.net/a83610312/article/details/12685653
[2] http://www.cnblogs.com/jackge/p/3163835.html
实现代码:
网上关于本题的实现代码都是C语言写的, 而且有过多的计算. 本来根据用户的输入规模n, 直接计算n*n的矩阵就可以了, 但是网上的代码计算的是N*N, N是个预设的值, 而且比n大很多, 这样就影响了程序的速度.
描述
将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。
正整数n 的这种表示称为正整数n 的划分。
输入
标准的输入包含若干组测试数据。每组测试数据是一行输入数据,包括两个整数N 和 K。
(0 < N <= 50, 0 < K <= N)
输出
对于每组测试数据，输出以下三行数据:
第一行: N划分成K个正整数之和的划分数目
第二行: N划分成若干个不同正整数之和的划分数目
第三行: N划分成若干个奇正整数之和的划分数目
样例输入
5 2
样例输出
2
3
3
提示
第一行: 4+1, 3+2,
第二行: 5，4+1，3+2
第三行: 5，1+1+3， 1+1+1+1+1+1
分析
整数划分问题这几个变形确实很经典，需要一个个说明下：
设dp[n][m]表示数n划分方案中，每个数 不大于m 的划分数。
N划分成若干个可相同正整数之和
划分分两种情况：
- 划分中每个数都小于m：则划分数为dp[n][m-1]。
- 划分中至少有一个数等于m：则从n中减去去m，然后从n-m中再划分，则划分数为dp[n-m][m]。
动态转移方程：dp[n][m]=dp[n][m-1]+dp[n-m][m]。
N划分成若干个不同正整数之和
划分分两种情况：
- 划分中每个数都小于m：则划分数为dp[n][m-1]。
- 划分中至少有一个数等于m：则从n中减去m，然后从n-m中再划分，且再划分的数中每个数要小于m, 则划分数为dp[n-m][m-1]。
动态转移方程：dp[n][m]=dp[n][m-1]+dp[n-m][m-1]。
N划分成K个正整数之和
设dp[n][k]表示数n划分成k个正整数之和时的划分数。
划分分两种情况：
- 划分中不包含1：则要求每个数都大于1，可以先拿出k个1分到每一份，之后在n-k中再划分k份，即dp[n-k][k]。
- 划分中包含1：则从n中减去1，然后从n-1中再划分k-1份, 则划分数为dp[n-1][k-1]。
动态转移方程：dp[n][k]=dp[n-k][k]+dp[n-1][k-1]。
N划分成若干个奇正整数之和
设f[i][j]表示将数i分成j个正奇数，g[i][j]表示将数i分成j个正偶数。
首先如果先给j个划分每个分个1，因为奇数加1即为偶数，所以可得：
f[i-j][j] = g[i][j]。
划分分两种情况：
- 划分中不包含1：则要求每个数都大于1，可以先拿出k个1分到每一份，刚可将问题转换为”从i-j中划分j个偶数”，即g[i-j][j]。
- 划分中包含1：则从n中减去1，然后从n-1中再划分k-1份, 则划分数为dp[n-1][k-1]。
动态转移方程：f[i][j]=f[i-1][j-1]+g[i-j][j]。
#include <iostream> #include <cstring> using namespace std; #define N 51 int dp1[N][N]; //N划分成K个正整数之和的划分数目。 int dp2[N][N]; //N划分成若干个不同正整数之和的划分数目。 int dp3[N][N]; //N划分成若干个可相同的正整数之和的划分数目。 int f[N][N]; //N划分成K个奇正整数之和的划分数目。 int g[N][N]; //N划分成K个偶正整数之和的划分数目。 void initDivideInt() { memset(dp1, 0, sizeof(dp1)); //dp[n][k]=dp[n-k][k]+dp[n-1][k-1] memset(dp2, 0, sizeof(dp2)); //dp[n][m]=dp[n][m-1]+dp[n-m][m-1] memset(dp3, 0, sizeof(dp3)); //dp[n][m]=dp[n][m-1]+dp[n-m][m] for (int i = 1; i < N; i++) { for (int j = 1; j < N; j++) { if (i < j) { dp1[i][j] = 0; dp2[i][j] = dp2[i][i]; dp3[i][j] = dp3[i][i]; } else if (i == j) { dp1[i][j] = 1; dp2[i][j] = dp2[i][j - 1] + 1; dp3[i][j] = dp3[i][j - 1] + 1; } else { dp1[i][j] = dp1[i - j][j] + dp1[i - 1][j - 1]; dp2[i][j] = dp2[i][j - 1] + dp2[i - j][j - 1]; dp3[i][j] = dp3[i][j - 1] + dp3[i - j][j]; } } } } //f[i][j]=f[i-1][j-1]+g[i-j][j] void initDivideOdd() { f[0][0] = 1; g[0][0] = 1; for (int i = 1; i < N; i++) { for (int j = 1; j <= i; j++) { g[i][j] = f[i - j][j]; f[i][j] = f[i - 1][j - 1] + g[i - j][j]; } } } int main() { // freopen("in.txt", "r", stdin); int n, k; initDivideInt(); initDivideOdd(); while (cin >> n >> k) { cout << dp1[n][k] << endl; cout << dp2[n][n] << endl; int sum = 0; for (int i = 0; i <= n; i++) { sum += f[n][i]; } cout << sum << endl; } return 0; }
view plain copy /* 整数划分 （一）将n划分成若干不同整数之和的划分数 （二）将n划分成若干正整数之和的划分数 （三）将n划分成k个正整数之和的划分数 （四）将n划分成最大数不超过k的划分数 （五）将n划分成若干个 奇正整数之和的划分数 */ #include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<vector> #include<queue> #include<set> #include<map> #include<algorithm> #include<sstream> #define eps 1e-9 #define pi acos(-1) #define INF 0x7fffffff #define inf -INF #define MM 12900 #define N 50 using namespace std; typedef long long ll; const int _max = N + 10; int dp[_max][_max],n,k,out[6]; int main(){ #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); #endif // ONLINE_JUDGE while(scanf("%d%d",&n,&k)==2){ /*****************整数划分（二）******************/ memset(dp,0,sizeof(dp)); dp[0][0] = 1; for(int i = 0; i <= n; ++ i) for(int j = 1; j <= n; ++ j){ if(j>i)dp[i][j]=dp[i][i]; else dp[i][j] = dp[i-j][j] + dp[i][j-1]; } out[1] = dp[n][n]; /*****************整数划分（四）******************/ out[3] = dp[n][k]; /*****************整数划分（三）******************/ memset(dp,0,sizeof(dp)); dp[0][0] = 1; for(int i = 1; i <= N; ++ i) for(int j = 1; j <= i; ++ j){ dp[i][j] = dp[i-1][j-1]+dp[i-j][j]; } out[2] = dp[n][k]; /*****************整数划分（五）******************/ memset(dp,0,sizeof(dp)); dp[0][0] = 1; for(int i = 0; i <= n; ++ i) for(int j = 1; j <= n; ++ j){ if(j&1){ if(j>i)dp[i][j] = dp[i][i]; else dp[i][j] = dp[i-j][j]+dp[i][j-1]; } else dp[i][j] = dp[i][j-1]; } out[4] = dp[n][n]; /*****************整数划分（一）******************/ memset(dp,0,sizeof(dp)); dp[0][0] = 1; for(int i = 0; i <= n; ++ i) for(int j = 1; j <= n; ++ j){ if(j>i)dp[i][j]=dp[i][i]; else dp[i][j] = dp[i-j][j-1] + dp[i][j-1]; } out[5] = dp[n][n]; /*****************输出******************/ for(int i = 1; i<= 5; ++ i) printf("%d ",out[i]); printf(" "); } return 0; } /* /*****（一）将n划分成若干不同整数之和的划分数************ dp[i][j]表示将整数i划分成不超过j的划分数，分含不含j两种情况 dp[0][0] = 1 dp[i][j] = dp[i-j][j-1] + dp[i][j-1];(j<=i) = dp[i][i] (j >i) =>ans = dp[n][n] /*****（二）将n划分成若干正整数之和的划分数************* dp[i][j]表示将整数i划分成不超过j的划分数，分含不含j两种情况 与（一）区别，j可重复 dp[0][0] = 1 dp[i][j] = dp[i-j][j] + dp[i][j-1];(j<=i) = dp[i][i] (j >i) =>ans = dp[n][n] /*****（三）将n划分成k个正整数之和的划分数************* dp[i][j]表示将整数i划分成j个正整数的划分数，考虑j组数中含不含1 dp[0][0] = 1 dp[i][j] = dp[i-1][j-1] + dp[i-j][j]; 如果不包含1，那么每组数至少为2，从每堆数中各拿出1还能够成j堆数dp[i-j][j] =>ans = dp[n][k] /*****（四）将n划分成最大数不超过k的划分数************ dp[i][j]表示将整数i划分成不超过j的划分数，分含不含j两种情况 是（二）的特例 dp[0][0] = 1 dp[i][j] = dp[i-j][j] + dp[i][j-1];(j<=i) = dp[i][i] (j >i) =>ans = dp[n][k] /*****（五）将n划分成若干个 奇正整数之和的划分数****** dp[i][j]表示将整数i划分成不超过j的划分数，分含不含j两种情况 dp[0][0] = 1; j是奇数，正常判断 dp[i][j] = dp[i-j][j] + dp[i][j-1];(j<=i) = dp[i][i] (j >i) j是偶数,dp[i][j] = dp[i][j-1]//往下递推 =>ans = dp[n][n] */