硬币

问题陈述

硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)

1
2
3
4
5
 输入: n = 5
 输出：2
 解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution{
    public int waysToChange(int n){
        int[] dp=new int[n+1];
        int[] coins=new int[]{1,5,10,25};
        
        dp[0]=1;//组成面值为0的硬币情况，即不使用任何硬币，也视为一种情况。
        for(int coin:coins){
            for(int i=coin;i<=n;i++){
                dp[i]=(dp[i]+dp[i-coin])%1000000007;
            }
        }
        return dp[n];
    }
}