【算法】整数划分

常规的整数划分

考虑对一个正整数 N 划分为若干个正整数的和，求所有方案数。

如当 时，所有的方案（共 7 种）如下：5、4 + 1、3 + 2、3 + 1 + 1、2 + 2 + 1、2 + 1 + 1 + 1、1 + 1 + 1 + 1 + 1。

 不难想出解决这个问题的一个有效方法是动态规划（分治法）。

若定义 为正整数 划分为若干正整数的和的所有方案数，会发现我们很难仅从 去推导出 ，事实上 与 均有关系。

一个合理的思路是，先取定一个加数 ，然后可以立即得到一个方案：

如何从上式推出更多方案呢？可以对继续划分，如固定一个加数 ，同理得到 ，那么就能得到 的另一个方案：

这样便可以将问题规模逐渐变小。当然这个思路是比较粗略的，原因在于目前这种定义的结构没有序：如果对固定的加数进行遍历，会重复计算相同的方案数（如 5 = 2 + 3 = 3 + 2），并且由于大量相同子问题的重复计算，时间复杂度也是很高的。

为了增加有序性，我们采用二维数组定义，定义 为正整数 i 划分为若干不大于 的正整数的和的所有方案数。在这个定义下，问题的答案即 ，并且很容易得到状态转移方程。

先考虑特殊情况，假如要计算一个 ，显然，按定义，不能存在大于 的加数。那么可分为下面两种情形：

• 若存在加数 ，则只有一种划分，即 ，方案数为1
• 若不存在加数 ，即所有加数都不大于 ，此时方案数即为

即当 时，我们有

当 时，由于加数不能为负数，我们有

当 时

• 若存在加数 ， 则此时划分等价于对 进行加数不大于 的划分，方案数为
• 若不存在加数 ，此时相当于对 进行加数不大于 的划分，这恰好符合 dp 的定义： 必定不含加数 ，即此时方案数为

即当 时，我们有

综上，状态转移方程为：

再考虑边界条件，1 只有一种划分，即1 = 1。且对任意正整数 i，加数不大于 1 的划分也只有一种，即 i 个 1 相加。边界条件为和

C语言实现：

unsigned q(unsigned n, unsigned m)
{
    int dp[n + 1][m + 1];
    memset(dp, -1, sizeof(dp));
    for(int i = 1; i <= n; i++)
    {
        dp[i][1] = 1;
    }

    for(int i = 1; i <= m; i++)
    {
        dp[1][i] = 1;
    }

    for(int i = 2; i <= n; i++)
    {
        for(int j = 2; j <= m; j++)
        {
            if(j > i) dp[i][j] = dp[i][i];
            else if(j == i) dp[i][j] = dp[i][i - 1] + 1;
            else dp[i][j] = dp[i][j - 1] + dp[i - j][j];
        }
    }
    
    //printArray2D(dp, n + 1, m + 1);
    return dp[n][m];
}

接下来解决这个问题的一些变体。

K个加数的划分

若规定分解的加数必须为个，那么计数的范围就减少了。一个直观的思路是依旧使用上面的划分方法，但是过滤掉加数个数不为的分解，但这样的话会有些麻烦。由于限定加数个数后，问题依旧具有最优子结构性质，我们还是可以通过动态规划的方式去解决，区别只是状态数组的定义和状态转移方程不同而已。

举例：当时，共有3 + 1 + 1、2 + 2 + 1两种。

依旧采用二维数组，定义 为正整数 i 划分为个正整数的和的所有方案数。在这个定义下，问题的答案即 。接下来考虑状态转移：

• 若，由于加数都是正整数，这样的划分不存在。方案数为0。
• 若，这样的划分只有一种，即 k 个 1 相加。方案数为1。
• 若，依旧分为两种情形
  • 若加数恰好全不为1，即先分配 k 个 1 作为所有的加数（由于，这样的分配总是可行的），再将余下的分配到这 k 个 1 上面，方案数为 。注意这种情形方案数可能为0
  • 若加数存在至少一个1，即先固定一个加数为1，再将余下的分解为个加数，方案数为

即可以得到如下的状态转移方程：

再考虑边界条件，显然有和

C语言实现：

unsigned q_k(unsigned n, unsigned k)
{
    int dp[n + 1][k + 1];
    memset(dp, -1, sizeof(dp));
    for(int i = 1; i <= n; i++)
    {
        dp[i][1] = 1;
    }

    for(int i = 2; i <= k; i++)
    {
        dp[1][i] = 0;
    }

    for(int i = 2; i <= n; i++)
    {
        for(int j = 2; j <= k; j++)
        {
            if(j > i) dp[i][j] = 0;
            else if(j == i) dp[i][j] = 1;
            else dp[i][j] = dp[i - j][j] + dp[i - 1][j - 1];
        }
    }
    return dp[n][k];
}

最多K个加数的划分

若规定加数最多为个，也可通过改变定义来求解。定义 为正整数 i 划分为最多个正整数的和的所有方案数。在这个定义下，问题的答案即 。

• 若，
• 若，
• 若，依旧分为两种情形
  • 若加数恰好有个，即先分配 k 个 1 作为所有的加数（由于，这样的分配总是可行的），再将余下的分配到这 k 个 1 上面，方案数为 。注意这种情形方案数可能为0
  • 若加数最多只有个，方案数为

状态转移方程为：

注意到这个转移方程和常规情形竟然是一致的，甚至边界条件也是相同的。边界条件为和。这说明使用动态规划解决背景不同的两个问题时，可能具有相同的结构！

具体到这个例子上，对正整数 进行划分，所有加数均不大于的划分方案数和加数个数不大于的划分方案数总是相等的。如时

• 所有加数均不大于，有3 + 2、3 + 1 + 1、2 + 2 + 1、2 + 1 + 1 + 1、1 + 1 + 1 + 1 + 1共5种
• 加数个数不大于，有5、4 + 1、3 + 2、3 + 1 + 1、2 + 2 + 1共5种

C语言实现：

unsigned q_maxk(unsigned n, unsigned k)
{
    int dp[n + 1][k + 1];
    memset(dp, -1, sizeof(dp));
    for(int i = 1; i <= n; i++)
    {
        dp[i][1] = 1;
    }

    for(int i = 1; i <= k; i++)
    {
        dp[1][i] = 1;
    }

    for(int i = 2; i <= n; i++)
    {
        for(int j = 2; j <= k; j++)
        {
            if(j > i) dp[i][j] = dp[i][i];
            else if(j == i) dp[i][j] = dp[i][i - 1] + 1;
            else dp[i][j] = dp[i][j - 1] + dp[i - j][j];
        }
    }
    return dp[n][k];
}

相异加数的划分

若规定加数不能相同，反而会比上面两种变体更简单些，只需对常规情形进行一点修改即可。定义 为正整数 i 划分为相异且不超过的正整数的和的所有方案数。在这个定义下，问题的答案即 。

容易得到状态转移方程：

C语言实现：

unsigned q_unique(unsigned n, unsigned m)
{
    int dp[n + 1][m + 1];
    memset(dp, -1, sizeof(dp));

    for(int i = 1; i <= m; i++)
    {
        dp[1][i] = 1;
    }

    for(int i = 2; i <= n; i++)
    {
        dp[i][1] = 0;
    }

    for(int i = 2; i <= n; i++)
    {
        for(int j = 2; j <= m; j++)
        {
            if(j > i) dp[i][j] = dp[i][i];
            else if(j == i) dp[i][j] = dp[i][i - 1] + 1;
            else dp[i][j] = dp[i][j - 1] + dp[i - j][j - 1];
        }
    }
    return dp[n][m];
}