0518. 零錢兌換 II · ttttt

# 0518. 零錢兌換 II ## 題目地址（518. 零錢兌換 II） <https://leetcode-cn.com/problems/coin-change-2/> ## 題目描述 ``` <pre class="calibre18">``` 給定不同面額的硬幣和一個總金額。寫出函數來計算可以湊成總金額的硬幣組合數。假設每一種面額的硬幣有無限個。示例 1: 輸入: 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 注意: 你可以假設： 0 <= amount (總金額) <= 5000 1 <= coin (硬幣面額) <= 5000 硬幣種類不超過 500 種結果符合 32 位符號整數 ``` ``` ## 前置知識 - [動態規劃](https://github.com/azl397985856/leetcode/blob/master/thinkings/dynamic-programming.md) - 背包問題 ## 公司 - 阿里 - 百度 - 字節 ## 思路這個題目和 coin-change 的思路比較類似。我們還是按照 coin-change 的思路來，如果將問題畫出來大概是這樣： ![](https://img.kancloud.cn/f1/1b/f11b98898dccc4675ef5b5f9219e6af4_558x433.jpg) 進一步我們可以對問題進行空間復雜度上的優化（這種寫法比較難以理解，但是相對更省空間） ![](https://img.kancloud.cn/c7/b1/c7b1841ee80cc8d58203f0b291e39229_681x394.jpg) > 這里用動圖會更好理解，有時間的話我會做一個動圖出來，現在大家腦補一下吧 ## 關鍵點解析 - 動態規劃 - 子問題用 dp\[i\] 來表示組成 i 塊錢，需要最少的硬幣數，那么 1. 第 j 個硬幣我可以選擇不拿這個時候，組成數 = dp\[i\] 2. 第 j 個硬幣我可以選擇拿這個時候，組成數 = dp\[i - coins\[j\]\] + dp\[i\] 3. 和 01 背包問題不同，硬幣是可以拿任意個，屬于完全背包問題 4. 對于每一個 dp\[i\] 我們都選擇遍歷一遍 coin，不斷更新 dp\[i\] eg: ``` <pre class="calibre18">``` if (amount === 0) return 1; const dp = [Array(amount + 1).fill(1)]; for (let i = 1; i < amount + 1; i++) { dp[i] = Array(coins.length + 1).fill(0); for (let j = 1; j < coins.length + 1; j++) { // 從1開始可以簡化運算 if (i - coins[j - 1] >= 0) { // 注意這里是coins[j -1]而不是coins[j] dp[i][j] = dp[i][j - 1] + dp[i - coins[j - 1]][j]; // 由于可以重復使用硬幣所以這里是j不是j-1 } else { dp[i][j] = dp[i][j - 1]; } } } return dp[dp.length - 1][coins.length]; ``` ``` - 當我們選擇一維數組去解的時候，內外循環將會對結果造成影響 ![](https://img.kancloud.cn/58/0d/580dfac7ed75d3565f269d75be217779_684x409.jpg) eg: ``` <pre class="calibre18">``` // 這種答案是不對的。 // 原因在于比如amount = 5, coins = [1,2,5] // 這種算法會將[1,2,2] [2,1,2] [2, 2, 1] 算成不同的 if (amount === 0) return 1; const dp = [1].concat(Array(amount).fill(0)); for (let i = 1; i < amount + 1; i++) { for (let j = 0; j < coins.length; j++) { if (i - coins[j] >= 0) { dp[i] = dp[i] + dp[i - coins[j]]; } } } return dp[dp.length - 1]; // 正確的寫法應該是內外循環調換一下, 具體可以看下方代碼區 ``` ``` ## 代碼代碼支持：Python3，JavaScript： JavaSCript Code: ``` <pre class="calibre18">``` /* * @lc app=leetcode id=518 lang=javascript * * [518] Coin Change 2 * */ /** * @param {number} amount * @param {number[]} coins * @return {number} */ var change = function (amount, coins) { if (amount === 0) return 1; const dp = [1].concat(Array(amount).fill(0)); for (let j = 0; j < coins.length; j++) { for (let i = 1; i < amount + 1; i++) { if (i - coins[j] >= 0) { dp[i] = dp[i] + dp[i - coins[j]]; } } } return dp[dp.length - 1]; }; ``` ``` Python Code: ``` <pre class="calibre18">``` class Solution: def change(self, amount: int, coins: List[int]) -> int: dp = [0] * (amount + 1) dp[0] = 1 for j in range(len(coins)): for i in range(1, amount + 1): if i >= coins[j]: dp[i] += dp[i - coins[j]] return dp[-1] ``` ``` **復雜度分析** - 時間復雜度：O(amount)O(amount)O(amount) - 空間復雜度：O(amount?len(coins))O(amount \* len(coins))O(amount?len(coins)) ## 擴展這是一道很簡單描述的題目，因此很多時候會被用到大公司的電面中。相似問題: [322.coin-change](322.coin-change.html) ## 附錄 Python 二維解法（不推薦，但是可以幫助理解）： ``` <pre class="calibre18">``` class Solution: def change(self, amount: int, coins: List[int]) -> int: dp = [[0 for _ in range(len(coins) + 1)] for _ in range(amount + 1)] for j in range(len(coins) + 1): dp[0][j] = 1 for i in range(amount + 1): for j in range(1, len(coins) + 1): if i >= coins[j - 1]: dp[i][j] = dp[i - coins[j - 1]][j] + dp[i][j - 1] else: dp[i][j] = dp[i][j - 1] return dp[-1][-1] ``` ``` **復雜度分析** - 時間復雜度：O(amount?len(coins))O(amount \* len(coins))O(amount?len(coins)) - 空間復雜度：O(amount?len(coins))O(amount \* len(coins))O(amount?len(coins)) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經 37K star 啦。大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)