百练04简单的整数划分问题
原文地址：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样例输出
72
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>usingnamespace 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];
}
elseif (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;
}
return0;
}
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
usingnamespace std;
typedef longlong ll;
constint _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\n",out[i]);
printf("\n");
}
return0;
}
/*
/*****（一）将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]
*/
分析3
以上是 百练04简单的整数划分问题 的全部内容， 来源链接： utcz.com/z/509297.html
