题目
题目链接
硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)
示例1:
输入: n = 5输出：2解释: 有两种方式可以凑成总金额:5=55=1+1+1+1+1
示例2:
输入: n = 10输出：4解释: 有四种方式可以凑成总金额:10=1010=5+510=5+1+1+1+1+110=1+1+1+1+1+1+1+1+1+1
说明：
注意:
你可以假设：
0 <= n (总金额) <= 1000000
解题思路
题目要求，每个硬币可以多次选择。
备选硬币有两种状态，
在备选硬币符合条件的情况下（备选硬币值小于需要组成的面值）选择当前备选硬币在备选硬币不符合条件情况下，不选择当前备选硬币
状态确定了
定义dp数组 dp[][]
dp[i][j] 表示i种硬币组成面值j时有多少种方法
于是状态转移方程就确定了
当前硬币不选：dp[i][j]=dp[i-1][j]当前硬币选择：dp[i][j]=dp[i][j-coins[i-1]]当前硬币选择与不选择都可以：dp[i][j] = (dp[i - 1][j] + dp[i][j - coins[i-1]])
于是乎初始条件也可以确定了
dp[0][j] ： 0 种硬币组成面值 j，不可能有方案，因此是 0dp[i][0]： 多种硬币组成面值 0，只有一种方案，一枚也不选
代码
class Solution {public int waysToChange(int n) {int[] coins = new int[]{1, 5, 10, 25};int[][] dp = new int[5][n + 1]; // base casefor (int i = 1; i <= 4; i++) {//多种硬币组成面值 0，只有一种方案，就是一枚也不选dp[i][0] = 1;}for (int i = 1; i <= 4; i++) {for (int j = 1; j <= n; j++) {if (j - coins[i-1] < 0){// 在备选硬币不符合条件情况下，不选择当前备选硬币dp[i][j] = dp[i - 1][j] % 1000000007; // 只能由 i - 1 中硬币来组成面值 j} else {// 当前硬币可以选择 也可以不选 如果当前硬币选择那么是一个组成方式，如果当前硬币不选择又是一个组成方式 结果一定是两者相加dp[i][j] = (dp[i - 1][j] + dp[i][j - coins[i-1]]) % 1000000007;}}}return dp[4][n];}}
