首页 > 代码库 > HDU 1028 整数划分问题 DP
HDU 1028 整数划分问题 DP
http://acm.hdu.edu.cn/showproblem.php?pid=1028
将一个正整数n划分成多个正整数的和,例如4可以划分为4,1 + 3,2 + 2,1 + 1 + 2, 1 + 1 + 1(1 + 3和3 + 1算作一种划分)。
在网上找到了两种做法
方法1:
dp[i][j] 的含义是将一个正整数i划分为j个整数的和有几种分法。转移方程很好写但是不太好想。
将此划分分为两种情况,划分中包括1和不包括1。若划分中包括1,则只需将剩余的整数i - 1划分成j - 1个整数即可。若划分中不包括1,则相当于将此时的方案数等于dp[i - j][j],因为只要将i - j划分为j个整数,再将每个整数都加1,就可以保证所有整数都不为1,且他们的加和为i。
综上,这种方法的转移方程为dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j],对于一个整数n,最终答案即为dp[n][1] + dp[n][2] + ... + dp[n][n]
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <string.h> #define MAX 125 int main() { int dp[MAX][MAX], res[MAX], n, i, j; memset(dp, 0, sizeof(dp)); memset(res, 0, sizeof(res)); dp[0][0] = 1; for(i = 1; i < MAX; i++) for(j = 1; j <= i ; j++) dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j]; for(i = 1; i < MAX; i++) for(j = 1; j <= i; j++) res[i] += dp[i][j]; while(scanf("%d", &n) != EOF) printf("%d\n", res[n]); return 0; }
方法2
这种方法中dp[i][j]的含义是将一个整数i划分为多个最大值不超过j的整数的方案数。
当i > j时,可以分为划分中存在j和不存在j两种情况,若不存在j,则相当于将i划分为最大值为j - 1的整数。若存在j,将剩余的i-j划分为不大于j的整数即可。
当i = j时,若划分中存在j显然只有一种情况,若不存在j,情况同上。
当i < j时,因为不能将i划分出大于i的整数,所以此时情况与dp[i][i]相同。
综上 i > j 时 dp[i][j] = dp[i - j][j] + dp[i][j - 1];
i = j 时 dp[i][j] = 1 + dp[i][j - 1];
i < j 时 dp[i][j] = dp[i][i];
最终答案即为dp[n][n]
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <string.h> #define MAX 125 int main() { int dp[MAX][MAX], res[MAX], n, i, j; memset(dp, 0, sizeof(dp)); memset(res, 0, sizeof(res)); dp[0][0] = 1; for(i = 1; i < MAX; i++) for(j = 1; j < MAX ; j++){ if(i == j) dp[i][j] = 1 + dp[i][j - 1]; else if(i > j) dp[i][j] = dp[i - j][j] + dp[i][j - 1]; else if(i < j) dp[i][j] = dp[i][i]; } while(scanf("%d", &n) != EOF) printf("%d\n", dp[n][n]); return 0; }
HDU 1028 整数划分问题 DP