整数分区（算法和递归）

小编典典

整数分区（算法和递归）

algorithm

查找总和数（代码中的变量 n ）的组合数。例如：

3 = 1 + 1 + 1 = 2 + 1 = 3 => ANS为3

5 = 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 +
1 + 1 => ANS为7

在下面的示例中， m 是最大数并且n是总和，目的是查找它具有多少个（总和）组合。

我只想知道为什么p(n, m) = p(n, m - 1) + p(n - m, m)？

这里的代码：

int p (int n, int m)
{
    if (n == m)
        return 1 + p(n, m - 1);
    if (m == 0 || n < 0)
        return 0;
    if (n == 0 || m == 1)
        return 1;

    return p(n, m - 1) + p(n - m, m);

}

感激！

阅读 302

2020-07-28

共1个答案

小编典典

考虑n通过将小于或等于的一些数字相加得出的所有方法m。如您所说，我们称之为p(n,m)。例如，p（7,3）=
8是因为有8种方法可以使小于3的数字中的7个如下所示：（为简单起见，我们可以假设总是按从大到小的顺序添加数字）

3 + 3 + 1
3 + 2 + 2
3 + 2 + 1 + 1
3 + 1 + 1 + 1 + 1
2 + 2 + 2 + 1
2 + 2 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1 + 1

现在我们可以将这些组合分为两组：

第一个元素等于m（在我们的示例中为= 3）的组合
- 3 + 3 + 1
- 3 + 2 + 2
- 3 + 2 + 1 + 1
- 3 + 1 + 1 + 1 + 1
- 第一个元素小于的组合m：
- 2 + 2 + 2 + 1
- 2 + 2 + 1 + 1 + 1
- 2 + 1 + 1 + 1 + 1 + 1
- 1 + 1 + 1 + 1 + 1 + 1 + 1

因为的每个组合成员p(n,m)都将在Group1或Group2中，所以我们可以说p(n,m)=size(Group1) + size(Group2)。现在，如果我们证明这一点size(Group1)=p(n-m, m)并size(Group2)=p(n,m-1)通过替代我们可以达到p(n,m)=p(n-m,m)+p(n,m-1)

证明`size(Group1)=p(n-m, m)`：

通过上述定义，p(n-m, m)是n-m通过添加一些小于或等于的数字得到的方法数量m。

如果将追加m到的每个组合p(n-m, m)，则将成为Group1的成员。所以p(n-m, m) <= size(Group1)
如果首先删除mGroup1的每个成员，则将产生的组合p(n-m, m)。所以size(Group1) <= p(n-m, m)

=> size(Group1) = p(n-m, m)。在我们的示例中：

组1 <===对应===> p（4，3）：

7 = 3 + 3+1<===========> 3+1= 4
7 = 3 + 2+2<===========> 2+2= 4
7 = 3 + 2+1+1<=======> 2+1+1= 4
7 = 3 + 1+1+1+1<===> 1+1+1+1= 4

因此，p(n-m,m)和组1的任何成员之间存在一对一的对应关系，并且它们的大小相等。

证明`size(Group2)=p(n, m-1)`：

根据定义，p(n,m-1)是n通过添加一些小于或等于m-1（小于m）的数字而得到的方法的数量。如果您重新阅读Group2的定义，您将看到这两个定义彼此相同。=> size(Group2) = p(n, m-1)

2020-07-28