获得总计的方式数量

Created: November-22, 2018

鉴于不同面额和总数的硬币，我们可以通过多少种方式将这些硬币结合起来获得总额？假设我们有 coins = {1, 2, 3} 和 total = 5，我们可以用 5 种方式获得总数：

1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
2 3

这个问题与背包问题密切相关。唯一的区别是我们有无限量的硬币供应。我们将使用动态编程来解决这个问题。

我们将使用 2D 数组 dp [n] [total + 1] ，其中 n 是我们拥有的不同硬币面额的数量。对于我们的例子，我们需要 dp [3] [6] 。这里 dp [i] [j] 将表示如果我们从硬币[0] 到硬币[i] 有硬币我们可以获得 j 的方式。例如， dp [1] [2] 将存储如果我们有硬币[0] 和硬币[1] ，我们可以用多少种方式制作 2 。让我们开始： **** **** **** **** **** ****

对于 dp [0] [0] ，我们问自己，如果我们只有 1 个面额的硬币，即硬币[0] = 1 ，我们可以通过多少种方式获得 0 ？答案是 1 路，这就是如果我们不采取任何硬币的。继续， dp [0] [1] 将代表我们只有硬币[0] ，我们可以通过多少种方式获得 1 ？答案是 1 。以相同的方式， dp [0] [2] ， dp [0] [3] ， dp [0] [4] ， dp [0] [5] 将为 1 。我们的数组看起来像：

     +---+---+---+---+---+---+---+
(den)|   | 0 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
 (1) | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
     +---+---+---+---+---+---+---+
 (2) | 1 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
 (3) | 2 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+

对于 dp [1] [0] ，我们问自己是否有 2 个面额的硬币，即如果我们有硬币[0] = 1 而硬币[1] = 2 ，我们可以用多少种方式制作 0 ？答案是 1 ，这是完全没有硬币。对于 dp [1] [1] ，由于硬币[1] = 2 大于我们当前的总数， 2 将无助于获得总数。所以我们将排除 2 并计算我们可以使用硬币获得总数的方式 [0] 。但是这个值已经存储在 dp [0] [1]中 ！所以我们将从顶部获取价值。我们的第一个公式

if coins[i] > j
    dp[i][j] := dp[i-1][j]
end if

对于 dp [1] [2] ，我们可以通过多少种方式得到 2 ，如果我们有面额 1 和 2 的硬币？我们可以使 2 枚使用硬币的面额的 1 ，其由下式表示 DP [0] [2] ，再次我们可以采取 1 种的面额 2 ，其被存储在 DP [1] [2-硬币[I]] ，其中我 = 1 。为什么？如果我们看下一个例子就会很明显。对于 dp [1] [3] ，如果我们有 1 和 2 的面额硬币，我们可以通过多少种方式获得 3 ？我们可以做 3 **** **** **** 使用币值的硬币 1 在 1 种方式，其被存储在 DP [0] [3] 。现在，如果我们取 1 的面额为 2 ，我们需要 3 - 2 = 1 来得到总数。使用面额 1 和 2 的硬币获得 1 的方式的数量存储在 dp [1] [1]中，其可以写为 dp [i] [j-coins [i]] ，其中 i = 1 。这就是我们以这种方式编写前一个值的原因。我们的第二个也是最后一个公式是： **** **** **** **** **** ****

if coins[i] <= j
    dp[i][j] := dp[i-1][j] + dp[i][j-coins[i]]
end if

这是填充整个 dp 数组所需的两个公式。填满阵列后会看起来像：

     +---+---+---+---+---+---+---+
(den)|   | 0 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
 (1) | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
     +---+---+---+---+---+---+---+
 (2) | 1 | 1 | 1 | 2 | 2 | 3 | 3 |
     +---+---+---+---+---+---+---+
 (3) | 2 | 1 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+

dp [2] [5] 将包含我们所需的答案。算法：

Procedure CoinChange(coins, total):
n := coins.length
dp[n][total + 1]
for i from 0 to n
    dp[i][0] := 1
end for
for i from 0 to n
    for j from 1 to (total + 1)
        if coins[i] > j
            dp[i][j] := dp[i-1][j]
        else
            dp[i][j] := dp[i-1][j] + dp[i][j-coins[i]]
        end if
    end for
end for
Return dp[n-1][total]

该算法的时间复杂度为 O(n * total)，其中 n 是我们拥有的硬币的面额数。