【算法】整数划分

常规的整数划分

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

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

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

若定义 \(dp[i]\) 为正整数 \(i\) 划分为若干正整数的和的所有方案数，会发现我们很难仅从 \(dp[i - 1]\) 去推导出 \(dp[i]\)，事实上 \(dp[i]\) 与 \(dp[1],dp[2],..., dp[i - 1]\) 均有关系。

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

\(N = X + (N - X)\)

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

\(N = X + Y + (N - X - Y)\)

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

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

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

• 若存在加数 \(i\)，则只有一种划分，即 \(i = i\)，方案数为1
• 若不存在加数 \(i\)，即所有加数都不大于 \(i - 1\)，此时方案数即为 \(dp[i, i - 1]\)

即当 \(i = m\) 时，我们有 \(dp[i, m] = 1 + dp[i, i - 1]\)

当 \(i < m\) 时，由于加数不能为负数，我们有 \(dp[i, m] = dp[i, i]\)

当 \(i > m\) 时

• 若存在加数 \(m\)，\(i = m + (i - m)\) 则此时划分等价于对 \(i - m\) 进行加数不大于 \(m\) 的划分，方案数为\(dp[i - m, m]\)
• 若不存在加数 \(m\)，此时相当于对 \(i\) 进行加数不大于 \(m - 1\) 的划分，这恰好符合 dp 的定义：\(dp[i , m - 1]\) 必定不含加数 \(m\)，即此时方案数为 \(dp[i, m - 1]\)

即当 \(i > m\) 时，我们有 \(dp[i, m] = dp[i - m, m] + dp[i, m - 1]\)

综上，状态转移方程为：

再考虑边界条件，1 只有一种划分，即1 = 1。且对任意正整数 i，加数不大于 1 的划分也只有一种，即 i 个 1 相加。边界条件为\(\forall m,dp[1, m] =1\)和\(\forall i,dp[i, 1] =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个加数的划分

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

举例：当\(N = 5, K = 3\)时，共有3 + 1 + 1、2 + 2 + 1两种。

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

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

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

再考虑边界条件，显然有\(\forall k>1,dp[1, k] =0\)和\(\forall i,dp[i, 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个加数的划分

若规定加数最多为\(K\)个，也可通过改变定义来求解。定义\(dp[i, k]\) 为正整数 i 划分为最多\(k\)个正整数的和的所有方案数。在这个定义下，问题的答案即 \(dp[N, K]\)。

• 若\(k > i\)，\(dp[i, k] = dp[i, i]\)
• 若\(k = i\)，\(dp[i, k] = 1 + dp[i, i - 1]\)
• 若\(k < i\)，依旧分为两种情形
  • 若加数恰好有\(K\)个，即先分配 k 个 1 作为所有的加数（由于\(k<i\)，这样的分配总是可行的），再将余下的\(i - k\)分配到这 k 个 1 上面，方案数为 \(dp[i-k,k]\)。注意这种情形方案数可能为0
  • 若加数最多只有\(K - 1\)个，方案数为\(dp[i, k - 1]\)

状态转移方程为：

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

具体到这个例子上，对正整数 \(N\)进行划分，所有加数均不大于\(k\)的划分方案数和加数个数不大于\(k\)的划分方案数总是相等的。如\(N = 5, K=3\)时

• 所有加数均不大于\(K=3\)，有3 + 2、3 + 1 + 1、2 + 2 + 1、2 + 1 + 1 + 1、1 + 1 + 1 + 1 + 1共5种
• 加数个数不大于\(K=3\)，有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];
}

相异加数的划分

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

容易得到状态转移方程：

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];
}