溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
小編給大家分享一下golang刷leetcode技巧之如何解決硬幣問題，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！
硬幣。給定數量不限的硬幣，幣值為25分、10分、5分和1分，編寫代碼計算n分有幾種表示法。(結果可能會很大，你需要將結果模上1000000007)
示例1:
輸入: n = 5
輸出：2
解釋: 有兩種方式可以湊成總金額:
5=5
5=1+1+1+1+1
示例2:
輸入: n = 10
輸出：4
解釋: 有四種方式可以湊成總金額:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1
說明：
注意:
你可以假設：
0 <= n (總金額) <= 1000000
解題思路：
1，注意和上一篇，爬樓梯的相似點和區別
面額dp[i]!=sum(dp[i-coins[j]])
因為如果dp[i-coins[j]]全部由面額為coins[j]的硬幣組成，那么dp[i]應該是1 而不是累加。爬樓梯需要累加
2，狀態轉移方程
令 dp[i][j] 為遍歷到當下i這個硬幣時，組成金額 j 的方法數目，有兩種可能性：
（1）當前這個硬幣沒有取，dp[i][j]=dp[i-1][j]；
（2）當前這個硬幣取了，dp[i][j]=dp[i][j-coins[i]]
最后的結果是兩者的和
如果j<dp[i][j-coins[i]],則，不應該計入（2）
注意：硬幣面值也需要升序
代碼實現
func waysToChange(n int) int {coins:=[]int{1,5,10,25}/*dp:=make([]int,n+1)dp[0]=1for i:=1;i<n+1;i++{for j:=0;j<len(coins);j++{if i>=coins[j]{dp[i]=(dp[i]+dp[i-coins[j]])%1000000007}}}//類似邁臺階，當時這里有個問題，如果上一個結果是用的1分面額，從上一個面額到當前面額還是用1分加的，這種情況不能算return dp[n]*//**令 dp[i][j] 為遍歷到當下這個硬幣時，組成金額 j 的方法數目有兩種可能性（1）當前這個硬幣沒有取，dp[i][j]=dp[i-1][j]；（2）當前這個硬幣取了，dp[i][j]=dp[i][j-coins[i]]。最后的結果是兩者的和將狀態轉移方程翻譯成代碼，并處理邊界條件*/dp:=make([][]int, 4)for i:=0;i<4;i++{dp[i]=make([]int,n+1)}for i:=0;i<n+1;i++{dp[0][i]=1}for i:=0;i<4;i++{dp[i][0]=1}for i:=1;i<4;i++{for j:=1;j<=n;j++{if j>=coins[i]{dp[i][j]=(dp[i-1][j]+dp[i][j-coins[i]])%1000000007}else{dp[i][j]=dp[i-1][j]}}}return dp[3][n]}
看完了這篇文章，相信你對“golang刷leetcode技巧之如何解決硬幣問題”有了一定的了解，如果想了解更多相關知識，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
