整数划分

发表于 | 分类于

整数划分总结

1.把整数n划分成不大于m的划分的种类数

  • 允许有重复的情况，eg：5 = 1 + 2 + 2，我们定义dp二维数组 ,注意当n>m时分成两部分：①不含m时dp(n)(m-1)，②至少含有一个m时dp(n-m)(m)，代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    /**
    dp[n][m] = dp[n][n]; (n < m)
    dp[n][m] = dp[n][m-1] + 1; (n = m)
    dp[n][m] = dp[n][m-1] + dp[n-m][m]; (n > m)
    */
    for(int i=1; i<MAX; i++) {
        for(int j=1; j<MAX; j++) {
            if(i < j) {
                dp[i][j] = dp[i][i];
            }else if(i == j) {
                dp[i][j] = dp[i][j-1] + 1;
            }else {
                dp[i][j] = dp[i][j-1] + dp[i-j][j];
            }
        }
    }

  • 不允许含有重复的情况，eg：5 = 1 + 4，我们定义dp二维数组 ,注意当n>m时分成两部分：①不含m时dp(n)(m-1)，②至少含有一个m时dp(n-m)(m-1)，代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    /**
    dp[n][m] = dp[n][n]; (n < m)
    dp[n][m] = dp[n][m-1] + 1; (n = m)
    dp[n][m] = dp[n][m-1] + dp[n-m][m-1]; (n > m)
    */
    for(int i=1; i<MAX; i++) {
        for(int j=1; j<MAX; j++) {
            if(i < j) {
                dp[i][j] = dp[i][i];
            }else if(i == j) {
                dp[i][j] = dp[i][j-1] + 1;
            }else {
                dp[i][j] = dp[i][j-1] + dp[i-j][j-1];
            }
        }
    }

2.把整数n划分成m个数的划分的种类数

  • 注意n>m时候分成两部分：①不含数字1，先拿m个数给每个坑一个数字1，然后这m个坑再分n-m即dp(n-m)(m)，②至少有一个数字1即dp(n-1)(m-1)，代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    /**
    dp[n][m] = 0; (n < m)
    dp[n][m] = 1; (n = m)
    dp[n][m] = dp[n-m][m] + dp[n-1][m-1]; (n > m)
    */
    for(int i=1; i<MAX; i++) {
        for(int j=1; j<MAX; j++) {
            if(i > j) {
                dp[i][j] = 0;
            }else if (i == j) {
                dp[i][j] = 1;
            }else {
                dp[i][j] = dp[i-j][j] + dp[i-1][j-1];
            }
        }
    }

3.把整数n划分成若干个奇正整数之和的划分数

  • g(n)(m)：将n划分成m个偶数；f(n)(m)：将n划分成m个奇数，这个比较难，先看偶数g(n)(m)的分法：先拿出m个1填每个坑，然后把剩下的n-m分成j个奇数即f(n-m)(m)；再看奇数f(n)(m)的分法：①不含1的情况，先拿出m个1填坑，然后把剩的n-m分成m个偶数即g(n-m)(m)；②至少有一个1的情况即f(n-1)(m-1)。代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    /**
    g[0][0] = f[0][0] = 1;
    g[n][m] = f[n-m][m];
    f[n][m] = f[i-1][j-1] + g[i-j][j];
    */
    for(int i=1; i<MAX; 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];
        }
    }