CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
题目
面试题 08.11. 硬币
硬币。给定数量不限的硬币，币值为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
解法
这道题，咋一看，n这么大的数据量，感觉就要用动态规划来做，仔细想想是一道完全背包问题，感觉好久都没遇到了……（上一次遇到还是程序设计课堂实验课上遇到过……当时感觉真难），看到评论区的各种解答，也趁此机会好好学习一波，推荐看看官方的解答和背包九讲.
首先，使用 dp[i][j]表示前 i 种硬币组会成面值为 j 的所有组合的总数，然后每种硬币又可以取无限枚，所以根据完全背包的状态转移方程得出：dp[i][j] = dp[i-1][j](不取第i枚硬币) + dp[i-1][j-c[i]]（取第 i 枚硬币）。
class Solution {
const int mod = 1000000007;
public:
int waysToChange(int n) {
vector<int> dp(n+1,0);
vector<int> coins = {1,5,10,25};
dp[0] = 1;
for(int i=0;i<coins.size();i++){
for(int j=1;j<=n;j++){
if(j>=coins[i]){
dp[j] = (dp[j] + dp[j-coins[i]])%mod;
}
}
}
return dp[n];
}
};