有数量不限的硬币，币值为25分、10分、5分和1分，请编写代码计算n分有几种表示法。
给定一个int n，请返回n分有几种表示法。保证n小于等于100000，为了防止溢出，请将答案Mod 1000000007。
测试样例：
6返回：2参考骑着炮弹进城提到的dp方法
这里补充一些解释，如有错漏，还请指正。
我们用dp[i]（i属于1~n ） 表示组合成i元一共有几种方法。
首先所有的硬币组合问题都要有基础面值：1元。i的总组合方法一定等于i中最后coin元不用新面值的方法+最后coin元使用新面值的方法。
而最后coin元 使用新面值的方法必然等于i-coin的总组合方法。
不用新面值的方法就是旧值
假如只有1元，那对于任给的1~n，必然只有1中组合方法。
假设增加一种新面值：coin元。对于任意i（i属于1~n），
当i<coin的时候，新面值组合方法为0，dp[i]不变。
当i=coin，新组合方法为1，总dp[i]=旧dp[i]+1
当coin<i<2coin，新组合方法仍然为1，总dp[i]=旧dp[i] + 新dp[i-coin]
当i=2coin，仍然有总 dp[i]=旧dp[i] + 新dp[i- coin]
以coin=2为例
同样的道理，题目coin值取值为：[1 5 10 25]，迭代处理即可
代码如下：
class Coins {
public:
int countWays(int n) {
// write code here
int coins[4]={1,5,10,25};
int dp[100001]={0};
dp[0]=1;
for(int i=0;i<4;i++)
for(int j=coins[i];j<=n;j++)
dp[j] =(dp[j]+dp[j-coins[i]])%1000000007;
return dp[n];
}
};https://blog.csdn.net/cy13299138237/article/details/50474271
问题描述：
有数量不限的硬币，币值为25分、10分、5分和1分，请编写代码计算n分有几种表示法。
求解思路：
这也是典型的动态规划问题，我们可以这样考虑：当只有1分的硬币时，n从1到n分别有多少种表示方法；当有1分和5分的硬币时，n从1到n分别有多少种表示方法，因此类推，直到我们将1分、5分、10分和25分的硬币全部使用完。思想类似于0-1背包问题，0-1背包问题的具体求解方法可以参考我的上一篇博客动态规划之0-1背包问题。我们用数组coins[i]={1,5,10,25}表示各种币值，此时可以维护一张二维表ways[i][j],其中横坐标表示前i种表示币值，j表示硬币的总值，则ways[i][j]表示能用前i种硬币来表示j分的方法数。
当增加一种新的硬币币值时，有两种情况：
（1）不加入此种币值：ways[i][j]=ways[i-1][j];
（2）加入此种币值：加入该枚硬币之前的方法数为ways[i][j-coins[i]],那么加入该枚硬币之后构成j分的方法数也为ways[i][j-coins[i]]。
因此当增加一种新的币值时，j分的表示方法数为ways[i][j]=ways[i-1][j]+ways[i][j-coins[i]]。
代码实现：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] coins = {1, 5, 10, 25};
int[][] ways = new int[4][n + 1];
for (int i = 0; i < 4; i++)
ways[i][0] = 1; //第0行初始化为1
for (int j = 1; j <= n; j++)
ways[0][j] = 1; //第0列初始化为1
for (int i = 1; i < 4; i++) {
for (int j = 1; j <= n; j++) {
if (j >= coins[i])
ways[i][j] = ways[i - 1][j] + ways[i][j - coins[i]];
else
ways[i][j] = ways[i - 1][j];
}
}
System.out.println(ways[3][n]);
}
}
当然，维护二维表未免过于复杂，我们可以维护一张一维表，即用一维数组ways[j]来记录j分的表示方法数。改进的代码实现如下：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int []coins={1,5,10,25};
int []ways=new int[n+1];
ways[0]=1;
for(int i=0;i<4;i++){
for(int j=coins[i];j<=n;j++){
ways[j]=ways[j]+ways[j-coins[i]];
}
}
System.out.println(ways[n]);
}
}