C++刷leetcode（面试题 08.11. 硬币）【动态规划】

糖逗

题目描述：

1. 硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)
   
2. 
   
3. 示例1:
   
4. 
   
5. 输入: n = 5
   
6. 输出：2
   
7. 解释: 有两种方式可以凑成总金额:
   
8. 5=5
   
9. 5=1+1+1+1+1
   
10. 示例2:
    
11. 
    
12. 输入: n = 10
    
13. 输出：4
    
14. 解释: 有四种方式可以凑成总金额:
    
15. 10=10
    
16. 10=5+5
    
17. 10=5+1+1+1+1+1
    
18. 10=1+1+1+1+1+1+1+1+1+1
    
19. 说明：
    
20. 
    
21. 注意:
    
22. 
    
23. 你可以假设：
    
24. 
    
25. 0 <= n (总金额) <= 1000000
    
26. 
    
27. 来源：力扣（LeetCode）
    
28. 链接：https://leetcode-cn.com/problems/coin-lcci
    
29. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. int waysToChange(int n) {
   
2.         vector<int> dp(n+1, 0);
   
3.         vector<int> store = {1,5,10,25};
   
4.         dp[0] = 1;
   
5.         const int mod = 1e9+7;
   
6.         for(int j = 0; j < 4; j++){
   
7.             for(int i = store[j]; i <= n;i++){
   
8.                 dp[i] = (dp[i]+ dp[i-store[j]])%mod;
   
9.             }
   
10.         }
    
11.         return dp[n];
    
12.     }

复制代码

注意事项：https://leetcode-cn.com/problems ... o-wen-ti-by-eddiev/