每日一算--零錢兌換
給定不同面額的硬幣和一個總金額。寫出函式來計算可以湊成總金額的硬幣組合數。假設每一種面額的硬幣有無限個。
示例
輸入: amount = 5, coins = [1, 2, 5] 輸出: 4 解釋: 有四種方式可以湊成總金額: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 複製程式碼
示例
輸入: amount = 3, coins = [2] 輸出: 0 解釋: 只用面額2的硬幣不能湊成總金額3。 複製程式碼
示例
輸入: amount = 10, coins = [10] 輸出: 1 複製程式碼
日常找規律
瞬間想不到的話,就來分析找規律:
輸入: amount = 5, coins = [1, 2, 5]
- 有1、2、5三種類型的硬幣,選擇第一枚硬幣的時候有兩種方式,選擇1元或者不選擇1元。
- 選擇1元amount = 4; 不選擇1元 amount = 5 依次對每種型別的硬幣就像這樣選擇,直到amount為0的選擇,就是其中之一的解。
得出動態方程
dp(amount) = dp(i,amount-coins[i]) + dp(i++,amount) 邊界條件: amount-coins[i] < 0為無法湊出整數amount amount = 0找到符合的組合 i >= len(coins)所有硬幣型別都試過了 複製程式碼
實現方式
遞迴選擇實現
- 時間複雜度 O(2^n)
function change(coins, i, amount) { // 無法湊整 if (amount < 0) { return 0 } // 符合結果的組合 if (amount == 0) { return 1 } // 所有硬幣型別都試過了 if (i >= coins.length) { return 0 } // 選擇當前硬幣 + 不選擇當前硬幣 return change(coins, i, amount-coins[i]) + change(coins, i+1, amount) } 複製程式碼
優化遞迴實現
- 時間複雜度 O(m * n) 解法一中,會造成大量的重複計算,因此我們通過快取結果來提高效能。通過解法一,我們知道整個組合數就是:
- 對每種硬幣型別只有選和不選兩種結果 選擇後 amount = amount -(選擇的硬幣面額)
function change(coins, amount) { const dp = new Array(amount + 1) for (let i = 0; i < dp.length; i++) { if ( i === 0 ) { dp[i] = 1 } else { dp[i] = 0 } } for ( let i = 0; i < coins.length; i++) { for ( let j = 1; j <= amount; j++) { if ( coins[i] <= j) { dp[j] = dp[j] + dp[j- coins[i]] } } } return dp[amount] } 複製程式碼