整数划分问题

在本文中，我们将学习将解决划分问题和硬币找零问题的算法。请看下面的例子

3 = 2 + 1;

在上例中，我们可以看到 3 是 2 和 1 的相加。这意味着一个整数被表示为两个正整数的和。

考虑下表

正如我们在上表中观察到的，数字 1 可以用一种方式表示，即 1。数字 2 可以用两种方式表示，即 2 和 (1 + 1)。数字 3 可以用三种方式表示，即 3、(2 + 1) 和 (1 + 1 + 1)。数字 4 可以用五种方式表示，即 4、(3 + 1)、(2 + 2)、(2 + 1 + 1) 和 (1 + 1 + 1 + 1)。

P(n) 是将整数表示为正整数之和的方法数。

如果我们必须将 50 写成正整数的和，那么在纸上写出所有可能的划分是很困难的。我们需要某种算法来解决这个问题。

考虑下表

用于解决上述问题的方法

• 排除新硬币。
• 包含新硬币
• 添加 1 和 2。

现在我们需要填充空白列。

正如我们在上表中观察到的，要使用硬币 0 和 1 凑成 5，答案是 1。数学上，可以写成

集合 = {0, 1}

总计 = 5

要计算新单元格的值，还需要添加新硬币，即 2。我们需要找到新硬币对方法数的影响。

根据算法，我们首先从集合中排除新硬币。

集合 = {0, 1}

方法数为 1

现在，我们将新硬币包含在集合中。

集合 = {0, 1, 2}

当包含硬币 2 时，凑成 5 所需的剩余金额为 3。可以使用硬币 0、1 和 2 来凑成 3。使用硬币 0、1 和 2 凑成 3 的方法数为 2。因此，使用硬币 0、1 和 2 凑成 5 的总方法数为 (1 + 2) 3。

现在我们需要计算下一个单元格的值。在这种情况下，添加了新硬币，即 3，以凑成总计 5。

根据算法，我们首先排除硬币 3，然后集合可以写成

集合 = {0, 1, 2}

包含硬币 0、1 和 2 时凑成 5 的方法数为 3。现在我们将硬币，即 3，包含在集合中，然后集合可以写成

集合 = {0, 1, 2, 3}

当包含硬币 3 时，凑成 5 所需的剩余金额为 2。可以使用硬币 0、1、2 和 3 来凑成 2。使用硬币 0、1、2 和 3 凑成 2 的方法数为 2。因此，使用硬币 0、1、2 和 3 凑成 5 的总方法数为 (3 + 2) 5。

现在我们需要计算下一个单元格的值。在这种情况下，添加了新硬币，即 4，以凑成总计 5。

根据算法，我们首先排除硬币 4，然后集合可以写成

集合 = {0, 1, 2, 3}

包含硬币 0、1、2 和 3 时凑成 5 的方法数为 5。现在我们将硬币，即 4，包含在集合中，然后集合可以写成

集合 = {0, 1, 2, 3, 4}

当包含硬币 4 时，凑成 5 所需的剩余金额为 1。可以使用硬币 0、1、2、3 和 4 来凑成 1。使用硬币 0、1、2、3 和 4 凑成 1 的方法数为 1。因此，使用硬币 0、1、2、3 和 4 凑成 5 的总方法数为 (4 + 1) 5。

现在我们需要计算下一个单元格的值。在这种情况下，添加了新硬币，即 5，以凑成总计 5。

根据算法，我们首先排除硬币 5，然后集合可以写成

集合 = {0, 1, 2, 3, 4}

包含硬币 0、1、2、3 和 4 时凑成 5 的方法数为 5。现在我们将硬币，即 5，包含在集合中，然后集合可以写成

集合 = {0, 1, 2, 3, 4, 5}

当包含硬币 5 时，凑成 5 所需的剩余金额为 0。可以使用硬币 0、1、2、3、4 和 5 来凑成 0。使用硬币 0、1、2、3、4 和 5 凑成 0 的方法数为 1。因此，使用硬币 0、1、2、3、4 和 5 凑成 5 的总方法数为 (5 + 1) 6。

让我们看看一个表的所有值是如何计算的。

当硬币值为 0 时。

要计算第一个单元格的值，当硬币为 0 且我们必须计算用硬币 0 凑成 0 的方法数时。使用硬币 0 凑成 0 只有 1 种方法。

无法使用硬币 0 凑成 1，所以我们在单元格中放入 0，如下所示

同样，无法使用硬币 0 凑成 2、3、4 和 5，所以我们在下面表格中放入 0

现在在集合中添加了新硬币，即 1。现在我们有一个包含两个硬币的集合，即 0 和 1。由于新添加的硬币，即 1，对凑成 0 的方法数没有影响，所以我们复制上面单元格的值，即 1，如下表所示

要凑成 1，硬币 1 本身就被使用。因此，如上表所示，使用硬币 0 和 1 凑成 1 只有一种方法。

要凑成 2，使用了两个 1 硬币。因此，如上表所示，使用硬币 0 和 1 凑成 2 只有一种方法。

要凑成 3，使用了三个 1 硬币。因此，如上表所示，使用硬币 0 和 1 凑成 3 只有一种方法。

要凑成 4，使用了四个 1 硬币。因此，如上表所示，使用硬币 0 和 1 凑成 4 只有一种方法。

要凑成 5，使用了五个 1 硬币。因此，如上表所示，使用硬币 0 和 1 凑成 5 只有一种方法。

现在将新硬币添加到集合中，即 2。所以，我们有一个包含三个硬币的集合，即 0、1 和 2。使用硬币 0、1 和 2 凑成 0 只有一种方法，如下所示

新添加的硬币，即 2，对总和 1 没有影响。使用硬币 0 和 1 凑成 1 的方法数是 1，如下表所示。

要凑成 2，我们首先从集合中排除硬币 2。使用硬币 0 和 1 凑成 2 的方法数为 1。然后我们将在集合中包含硬币 2。因此，凑成 2 的总方法数为 (1+1) 2。

要凑成 3，我们首先从集合中排除硬币 2。使用硬币 0 和 1 凑成 3 的方法数为 1。然后我们将在集合中包含硬币 2。因此，凑成 3 的总方法数为 (1+1) 2。

要凑成 4，我们首先从集合中排除硬币 2。使用硬币 0 和 1 凑成 4 的方法数为 1。然后我们将在集合中包含硬币 2。因此，凑成 4 的总方法数为 (1+2) 3。

现在硬币的值是 3。集合中有 4 个硬币，即 0、1、2 和 3。使用硬币 0、1、2 和 3 凑成硬币 0 的方法数为 1，因此我们在单元格中加 1，如下表所示。

现在，集合中有四个硬币，即 0、1、2 和 3。由于硬币 2 和 3 大于 1，因此这些硬币没有影响。使用硬币 0 和 1 凑成 1 的方法数为 1。所以，我们在单元格中加 1，如下表所示。

硬币 3 大于 2，因此对总和 2 没有影响。使用硬币 0、1 和 2 凑成 2 的方法数为 2，因此我们在单元格中加 3，如下表所示。

现在总和的值是 3。我们有一个包含 {0, 1, 2, 3} 的集合。根据算法，我们首先排除新添加的硬币，即 3。使用 0、1 和 2 凑成 3 的方法数为 2。当将硬币 3 添加到集合中时，凑成 3 的总方法数为
(2 + 1) 3.

现在总和的值是 4。我们有一个包含 {0, 1, 2, 3} 的集合。根据算法，我们首先排除新添加的硬币，即 3。使用 0、1 和 2 凑成 4 的方法数为 3。当将硬币 3 添加到集合中时，凑成 4 的总方法数为
(3 + 1) 4.

现在总和的值是 0。我们有一个包含 {0, 1, 2, 3, 4} 的集合。使用硬币 0、1、2、3 和 4 凑成 0 只有一种方法，因此在单元格中加 1，如下表所示。

现在总和的值是 1。我们有一个包含 {0, 1, 2, 3, 4} 的集合。由于 4 大于 1，因此对 1 的值没有影响。使用硬币 0、1、2 和 3 凑成 1 的方法数为 1。因此，使用硬币 (0, 1, 2, 3 和 4) 凑成 1 的总方法数为 1。

现在总和的值是 2。我们有一个包含 {0, 1, 2, 3, 4} 的集合。由于 4 大于 2，因此对 2 的值没有影响。使用硬币 0、1、2 和 3 凑成 2 的方法数为 2。因此，使用硬币 (0, 1, 2, 3 和 4) 凑成 2 的总方法数为 2。

现在总和的值是 3。我们有一个包含 {0, 1, 2, 3, 4} 的集合。由于 4 大于 3，因此对 3 的值没有影响。使用硬币 0、1、2 和 3 凑成 3 的方法数为 3。因此，使用硬币 (0, 1, 2, 3 和 4) 凑成 3 的总方法数为 3。

现在总和的值是 4。我们有一个包含 {0, 1, 2, 3, 4} 的集合。新添加的硬币是 4。首先，我们排除硬币 4，那么集合中的硬币是 0、1、2 和 3。使用硬币 0、1、2 和 3 凑成 4 的方法数为 4。现在我们包含硬币 4，那么使用硬币 (0, 1, 2, 3, 4) 凑成 4 的方法数为 (4 + 1) 5。

现在总和的值是 0。我们有一个包含 {0, 1, 2, 3, 4, 5} 的集合。使用硬币 0、1、2、3、4 和 4 凑成 0 只有一种方法，因此在单元格中加 1，如下表所示。

现在总和的值是 1。我们有一个包含 {0, 1, 2, 3, 4, 5} 的集合。由于 5 大于 1，因此对 1 的值没有影响。使用硬币 0、1、2、3 和 4 凑成 1 的方法数为 1。因此，使用硬币 (0, 1, 2, 3, 4 和 5) 凑成 1 的总方法数为 1。

现在总和的值是 2。我们有一个包含 {0, 1, 2, 3, 4, 5} 的集合。由于 5 大于 2，因此对 2 的值没有影响。使用硬币 0、1、2、3 和 4 凑成 2 的方法数为 2。因此，使用硬币 (0, 1, 2, 3, 4 和 5) 凑成 2 的总方法数为 2。

现在总和的值是 3。我们有一个包含 {0, 1, 2, 3, 4, 5} 的集合。由于 5 大于 3，因此对 3 的值没有影响。使用硬币 0、1、2、3 和 4 凑成 3 的方法数为 3。因此，使用硬币 (0, 1, 2, 3, 4 和 5) 凑成 3 的总方法数为 3。

现在总和的值是 4。我们有一个包含 {0, 1, 2, 3, 4, 5} 的集合。由于 5 大于 4，因此对 4 的值没有影响。使用硬币 0、1、2、3 和 4 凑成 4 的方法数为 5。因此，使用硬币 (0, 1, 2, 3, 4 和 5) 凑成 5 的总方法数为 5。