整数划分问题

发表于 | 更新于 | 分类于 ，

1. 整数划分

对于任意一个正整数n，它可以表示为多个其他正整数相加。例如:

6 = 6 = 5 + 1 = 4 + 2 = 4 + 1 + 1 = 3 + 3 = 3 + 2 + 1 = 3 + 1 + 1 + 1...

我们称这种不同的组合为不同的整数划分。这类问题是经典的组合数学问题。常常要用到动态规划。

2. 经典整数划分问题

给定两个数，n和m。请问n的最大加数为不超过m的划分共有几种？这时一个较为经典的问题了，它的一个子问题就是当m ==n时的情况。

对于以上问题我们可以使用递归的思想，进行思考。

2.1 各个加数允许相同

那么不妨这样考虑。

  1. 一般情况下f(n, m)有何种特征？

    首先我们明确了对于任何m > n，都有f(n, m) == f(n, n)。

    然后我们进行递归的思考：将n按最大为m的划分有两种情况:

    • 划分中没有用到m

      这种情况下:

      1
      f(n, m) = f(n, m-1)

      ​

    • 划分中用到了m

      这种情况下我们就相当于把n划分为"m + ..."。所以:

      1
      f(n, m) = f(n-m, m)

      ​

    这样我们就可以对应的写出一个递归过程:

    1
    2
    3
    4
    if (n < m)
      	return f(n, n);
    else
      	return f(n, m-1) + f(n-m, m);

  2. 递归基是怎么样的？

    由于递归基基本就出现在0或1的情况下。所以为了考虑这个问题，我们只需要按照以下流程来思考就可以了:

    1. n == 0: 显然只有一种划分方式
    2. m == 0: 看情况，如果n == 0那么就有一种，反之则没有
    3. n == 1: 有且仅有一种
    4. m == 1: 有且仅有一种

    至此我们可以写出递归基来了:

    1
    2
    3
    4
    5
    6
    if (m == 0)
        return (n == 0)? 1 : 0;
    else if (n == 0)
     	return 1;
    else if (n == 1 || m == 1)//这两种情况都只有1种分法
      	return 1

经过以上分析我们可以写出整个算法程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private static long partiAsMaxIsMSamePermited(int n, int m)
{
    if (m == 0)
        return (n == 0)? 1 : 0;
    else if (n == 0)
        return 1;
    else if (n == 1 || m == 1)
        return 1;
    
    if (n < m)
        return partition(n, n);
	else
        return partition(n, m - 1) + partition(n - m, m);
}

然而以上程序可以继续简化，注意到对0的判断其实只是为了防止 n == m 这种情况的发生。因此完全可以简化逻辑判断:

1
2
3
4
5
6
7
8
9
10
private static long partiAsMaxIsMSamePermited(int n, int m)
{
    if (n == 1 || m == 1)
        return 1;
    
    if (n <= m)
        return partition(n, n - 1) + 1;
    else
        return partition(n, m - 1) + partition(n - m, m);
}

改写成非递归形式

我们可以运用动态规划的思想利用一个二维数组来模拟递归过程，从而将递归转换为非递归格式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private static long pSPDynamicPrgramming(int n, int m)
{
    int[][] res = new int[n + 1][n + 1];
    //构造递归基，注意i从1开始,相当于把所有索引含0的抛弃掉
    for (int i = 1; i <= n; ++i)
    {
        res[i][1] = res[1][i] = 1;
    }
	//对m进行预处理
    m = (m > n)? n : m;
    int i = 1, j = 1;
    for (i = 1; i <= n; ++i)
    {
        for (j = 1; j <= m; ++j)
        {
            if (i <= j)
                res[i][j] = res[i][i-1] + 1;
            else
                res[i][j] = res[i][j-1] + res[i-j][j];
        }
    }
    return res[n][m];
}

这个技巧非常好用，一定要掌握。以后遇到类似的递推形式的递归程序，也可以使用相似的方法来转换为非递归程序。

2.2 各个加数不允许相同

这种情况下与之前相比不同之处在于递归式不一样了。此前我们的递归式如下:

1
f(n, m) = f(n, m-1) + f(n-m, m)

而现在不允许相同后，递归式子成了:

1
f(n, m) = f(n, m-1) + f(n-m, m-1) //注意m变成了m-1

道理也好懂。我们之前也讲到过，后面的式子代表了最大数m被用到了的情况，那么既然已经被用到了，在之后就不可以继续出现，故而将上限减一。

那么现在来看一看递归基的问题。此前我们的递归基是这样的:

1
2
if (n == 1 || m == 1)
    return 1;

现在来分析一下这种情况下的递归基:

  • n == 1: 显然由于m >= 1，无论如何都只有一种分法
  • m == 1: 这时情况就和之前不一样了
    • 如果n == 1，那么刚好一种情况
    • 反之，n >= 1，由于不允许有相同数，因此无法划分，返回0

经过分析，递归基如下:

1
2
3
4
if(n == 1)
    return 1;
else if(m == 1)
    return 0;

整个程序全貌如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
private static long partitionSameForbiden(int n, int m)
{
    //可以看到只更改了递归基
    if(n == 1)
        return 1;
    else if(m == 1)
        return 0;
    //一下内容和之前的相同
    if (n <= m)
        return partitionSameForbiden(n, n - 1) + 1;
    else
        return partitionSameForbiden(n, m - 1) + partitionSameForbiden(n - m, m - 1);
}

改为非递归形式(动态规划)

递归形式有利于我们分析，不过为了执行效率，我们现在就需要改成非递归了。方法同上:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private static long pSFDynamicPrgramming(int n, int m)
{
    int[][] res = new int[n + 1][n + 1];
    //构造递归基
    for (int i = 1; i <= n; ++i)
    {
        res[i][1] = 0;
        res[1][i] = 1;
    }
    
    m = (m > n)? n : m;
    int i = 0, j = 0;
    for (i = 1; i <= n; ++i)
    {
        for(j = 1; j <= m; ++j)
        {
            if (i <= j)
                res[i][j] = res[i][i-1] + 1;
            else
                res[i][j] = res[i][j-1] + res[i-j][j-1];
        }
    }
    return res[n][m];
}

3. 指定数目

这次我们变换策略，要求找出将n划分为k个部分的个数。即对于指定的数n，必须要求由k个数相加得到。

3.1 刚好划分为k个数

首先说明一个规律:

正如之前一样，这里我们也可以利用递归的思想来解决。

  1. 平凡情况可以怎么进行分割?

    对于一个一般的情况f(n, k)我们应该怎么递归的将其分解呢？我们会先试图从总体中拿走一个子问题，将问题的规模削减。 再上一个问题中，我们把“有没有用到m”作为一个子问题将整体分割。这里我们不妨将“在这k个数中有没有用到1”作为一个子问题。

    • 如果用到了1:

      显然问题的规模就缩减成了: 我们先用到了1，然后在试图用k-1个数来组成n-1。即:

      1
      f(n, k) = f(n-1, k-1)

    • 如果没有用到1:

      这就要保证每个数都>=2。为此我们可以这么做：

      1. 从n中拿出k，分给k个数。使他们都为1
      2. 在都为1的基础上，在划分剩下的n-k，以此保证这k个数都至少为2

      也就是说:

      1
      f(n, k) = f(n-k, k)

  2. 递归基是什么

    1. n == 1时:

      若k == 1，则结果为1；否则为0

    2. k == 1时:

      仅在n == 1时才为1

  3. 其他注意:

    若n < k，则结果必然为0

    若n == k，则结果必然为1

这样我们就可以写成基本的递归式了:

1
2
3
4
5
6
7
8
9
10
private static long partiAtk(int n, int k)
{
    if (n == 0 || k == 0)
        return (n == 0 && k == 0)? 1 : 0;

    if (n <= k)
        return (n == k)? 1 : 0;
    else
        return partiAtk(n-1, k-1) + partiAtk(n-k, k);
}

改为动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private static long partiAtkDP(int n, int k)
{
    if (k > n)
        return 0;

    int[][] res = new int[n+1][n+1];
    res[0][0] = 1;//递归基条件

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= i; ++j)//注意i < k的部分忽略掉
        {
            res[i][j] = res[i-1][j-1] + res[i-j][j];//i == j 时必然为1
        }
    }
    return res[n][k];
}

一个有趣的事实

事实上，可以证明将n刚好划分为k个部分这个问题和n刚好划分为最大加数刚好为k(可重用)问题是同解。

1
2
3
//下面这两个问题输出相同
System.out.println(i + "," + j + ": " + partiAtkDP(i, j));
System.out.println(i + "," + j + ": " + (pSPNoneRecursion(i, j) - pSPNoneRecursion(i, j-1)));

3.2 最大不超过k个数

显然最大不超过k个数就相当于将上题中的函数结果从1累加到k所得到的值，换而言之则有:

\[ Result = \sum^{k}_{i}partiAtk(n, i) \]

然而基于我们之前的到的一个有趣的结论可以推导出另一个更有趣的结论:

将n划分为最大不超过k个数相加 = 将n划分为最大加数不超过k(可重用)

\[ Result = \sum^{m}_{k = 1}partiAtk(n, k) = partiAsMaxIsM(n, m) \]

即

\[ f(n, m) = f(n, m-1) + f(n - m, m) \]

所以我们想要解决这个问题的话，只要把最开始的经典问题的代码套过来就可以了。

4. 具体问题：分苹果模型

这是一个极其常见的问题，它包括了许多的变形，大致的样子如下:

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法
1<=M，N<=10

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
#include <iostream>
#include <cstring>
using namespace std;

int store[11][11];

int f(int m, int n)
{
    if (store[m][n] == -1)
    {
        if (m == 1 || n == 1)
            store[m][n] = 1;
        //把5个苹果放在6个盘子里和放在5个盘子里是一样的
        else if (m < n)
            store[m][n] = f(m, m);
        else if (m == n)
            store[m][n] = f(m, n - 1) + 1;
        else
            store[m][n] = f(m, n - 1) + f(m - n, n);
    }
    return store[m][n];
}

int main()
{
    int m, n;
    memset(store, -1, sizeof(store));
    while (cin >> m >> n)
        cout << f(m, n) << endl;
    return 0;
}