算法

动态规划之整数划分

       整数划分可以分为以下几个问题：

将n划分为不大于m的划分法

  • 若是划分多个整数可以存在相同的：

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

  • 若是划分多个不同的整数：

    • 1
    2
    3
    4
    dp[n][m]= dp[n][m-1]+ dp[n-m][m-1]   dp[n][m]表示整数n的划分中，每个数不大于 m 的划分数。
    同样划分情况分为两种情况：
        a.划分中每个数都小于m,相当于每个数不大于 m-1,划分数为 dp[n][m-1].
        b.划分中有一个数为 m.在n中减去m,剩下相当对n-m进行划分，并且每一个数不大于m-1，故划分数为 dp[n-m][m-1]

    将n划分成k个数的划分法：

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

    将n划分成若干奇数的划分法：

    1
    2
    3
    4
    5
    6
    7
    g[i][j]:将i划分为j个偶数
    f[i][j]:将i划分为j个奇数
    g[i][j] = f[i - j][j];
    f[i][j] = f[i - 1][j - 1] + g[i - j][j];
    方法可以分为两类：
        第一类：i中拿出j个1分到每一份中，将剩余的i-j分成j个奇数
        第二类：一份包含奇数1，剩余的i-1分成j-1个奇数；另一种，每份至少大于1，将j个1拿出来分到每一份中，其余i-j分成j份

    代码如下所示(转载)：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    #include<stdio.h>
    #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 = 0; i < nmax; i++) {
            num[i][0] = 0, num[0][i] = 0, num1[i][0] = 0, num1[0][i] = 0, num2[i][0] =
                    0, num2[0][i] = 0;
        }
        for (i = 1; i < nmax; i++) {
            for (j = 1; j < nmax; j++) {
                if (i < j) {
                    num[i][j] = num[i][i];
                    num1[i][j] = num1[i][i];
                    num2[i][j] = 0;
                } else if (i == j) {
                    num[i][j] = num[i][j - 1] + 1;
                    num1[i][j] = num1[i][j - 1] + 1;
                    num2[i][j] = 1;

                } else {
                    num[i][j] = num[i][j - 1] + num[i - j][j];
                    num1[i][j] = num1[i][j - 1] + num1[i - j][j - 1];
                    num2[i][j] = num2[i - 1][j - 1] + num2[i - j][j];
                }
            }
        }
        f[0][0] = 1, g[0][0] = 1;
        for (i = 1; i < nmax; i++) {
            for (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() {
    #ifndef ONLINE_JUDGE
        freopen("data.in", "r", stdin);
    #endif
        int n, k, i, res0, res1, res2, res3, res4;
        init();
        while (~scanf("%d %d", &n, &k)) {
            res0 = num[n][n];
            res1 = num2[n][k];
            res2 = num[n][k];
            for (i = 0, res3 = 0; i <= n; i++) {
                res3 += f[n][i];
            }
            res4 = num1[n][n];
            printf("%d\n%d\n%d\n%d\n%d\n\n", res0, res1, res2, res3, res4);
        }
        return 0;
    }