# 獲得總計的方式數量

• 1 1 1 1 1
• 1 1 1 2
• 1 1 3
• 1 2 2
• 2 3

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


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


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


     +---+---+---+---+---+---+---+
(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]