給你一個整數(shù)數(shù)組 coins 表示不同面額的硬幣，另給一個整數(shù) amount 表示總金額拒贱。
請你計算并返回可以湊成總金額的硬幣組合數(shù)宛徊。如果任何硬幣組合都無法湊出總金額，返回 0 逻澳。
假設(shè)每一種面額的硬幣有無限個闸天。
題目數(shù)據(jù)保證結(jié)果符合 32 位帶符號整數(shù)。
例子
輸入：amount = 5, coins = [1, 2, 5]
輸出：4
解釋：有四種方式可以湊成總金額：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2：
輸入：amount = 3, coins = [2]
輸出：0
解釋：只用面額 2 的硬幣不能湊成總金額 3 斜做。
示例 3：
輸入：amount = 10, coins = [10]
輸出：1
提示：
1 <= coins.length <= 300
1 <= coins[i] <= 5000
coins 中的所有值 互不相同
0 <= amount <= 5000
解題思路
典型的動態(tài)規(guī)劃問題, 它利用了之前計算的結(jié)果來更新當前的結(jié)果苞氮，這是動態(tài)規(guī)劃的典型特點。
初始化： 我們創(chuàng)建一個數(shù)組 dp瓤逼，長度為 amount + 1笼吟，用來存儲每個金額對應(yīng)的組合數(shù)库物。
dp[0] 初始化為: 1，因為湊成金額 0, 只有一種贷帮，即不用任何硬幣艳狐。
遍歷硬幣： 我們遍歷給定的硬幣數(shù)組 coins。對于每個硬幣 coin皿桑，我們更新 dp 數(shù)組毫目。
更新 dp 數(shù)組：
- 對于每個硬幣
coin，我們從coin開始遍歷dp數(shù)組诲侮，直到amount镀虐。 - 對于每個金額
i，我們更新dp[i]的值沟绪。 - 更新規(guī)則是
dp[i] = dp[i] + dp[i - coin]刮便。這意味著湊成金額 i 的組合數(shù)等于之前計算的組合數(shù)(dp[i])加上湊成金額i - coin的組合數(shù)(dp[i - coin])。
對于每個硬幣绽慈，我們可以選擇使用它或不使用它恨旱。如果我們選擇使用這個硬幣，那么問題就變成了湊成金額 i - coin 的組合數(shù)坝疼，而i - coin 金額組合數(shù)在之前的步驟中計算過了搜贤。
返回結(jié)果： 最后，dp[amount] 就是我們要求的結(jié)果钝凶，即湊成總金額 amount 的組合數(shù)仪芒。
代碼：
未翻譯版
func change(_ amount: Int, _ coins: [Int]) -> Int {
var dp = [Int](repeating: 0, count: amount + 1)
dp[0] = 1
for coin in coins {
if coin > amount { return dp[amount] }
for i in coin...amount {
dp[i] += dp[i - coin]
}
}
return dp[amount]
}
翻譯版
func change(_ amount: Int, _ coins: [Int]) -> Int {
// 定義0 ~ amount 的可變數(shù)組, 代表 0 ~ 總金額 之間的所有情況
var dp = [Int](repeating: 0, count: amount + 1)
// 湊成總金額為0 的時候, 只有1種可能, 不掏
dp[0] = 1
// 遍歷硬幣數(shù)組
for coin in coins {
// 如果當前硬幣大于總金額, 直接返回 dp[amount]
// 例如: coins = [2], amount = 1 這種
// 或 coins = [2, 100, 101], amount = 3,
// 遍歷到 100 這種, 超過要求總金額, 沒必要繼續(xù)遍歷
if coin > amount { return dp[amount] }
// 遍歷 當前硬幣 ~ 總金額, 計算每種金額需要情況
for i in coin...amount {
// 湊成總金額 i 的方式
// 等于原來的組合數(shù) 加上湊成總金額 i - coin 的組合數(shù)
// 例如 coins = [1, 2, 3], amount = 5
// dp = [1, 0, 0, 0, 0, 0] 數(shù)組下標為對應(yīng)總金額
// 當 i = 1, 硬幣為1, 遍歷完
// dp = [1, 1, 1, 1, 1, 1]
// 總金額如果是 0, 1種情況
// 總金額如果是 1, 1種情況
// ...
// 總金額如果是 5, 1種情況, 1+1+1+1+1
// 當 i = 2, 硬幣為2, 須用2硬幣
// 那么總金額為2的情況,
// 為當前總金額2組合數(shù)+總金額0組合數(shù) 2+0
// 即 dp[2] + dp[0],
// dp[2] = dp[2] + dp[2 - 2] = dp[2] + dp[0]
// 同理, 須用2硬幣, 總金額為3的情況 2+1
// 為當前總金額3組合數(shù)+總金額1組合數(shù) 即 dp[3] + dp[1]
// dp[3] = dp[3] + dp[3 - 2] = dp[3] + dp[1]
// 同理, 須用2硬幣, 總金額為4的情況 2+2
// 為當前總金額4組合數(shù)+總金額2組合數(shù) 即 dp[4] + dp[2]
// dp[4] = dp[4] + dp[4 - 2] = dp[4] + dp[2]
// 同理, 須用2硬幣, 總金額為5的情況 2+3
// 為當前總金額4組合數(shù)+總金額3組合數(shù) 即 dp[5] + dp[3]
// dp[5] = dp[5] + dp[5 - 2] = dp[5] + dp[3]
dp[i] += dp[i - coin]
}
}
// 返回湊成總金額情況
return dp[amount]
}
時間復(fù)雜度:
，其中 n 是金額（amount）的大小耕陷，m 是硬幣種類（coins 數(shù)組的長度）的數(shù)量掂名。這是因為我們需要對每種硬幣進行遍歷，并且對每個金額從該硬幣面額到總金額進行更新哟沫。
空間復(fù)雜度:
饺蔑，其中 n 是金額（amount）的大小。我們需要一個長度為 n + 1 的數(shù)組來存儲從 0 到 n 的每個金額對應(yīng)的組合數(shù)嗜诀。
題目來源：力扣（LeetCode） 感謝力扣爸爸 :)
IOS 算法合集地址
