獲得總計的方式數量

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 是我們擁有的硬幣的面額數。