小编给大家分享一下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进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
