硬币。给定数量不限的硬币，币值为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）
注意：硬币面值也需要升序
代码实现
代码语言：javascript复制func waysToChange(n int) int {
coins:=[]int{1,5,10,25}
/*
dp:=make([]int,n 1)
dp[0]=1
for 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]])00000007
}
}
}
//类似迈台阶，当时这里有个问题，如果上一个结果是用的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]])00000007
}else{
dp[i][j]=dp[i-1][j]
}
}
}
return dp[3][n]
}
