首页 > 代码库 > 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