LeetCode: 硬币

[guodongxiaren]

https://leetcode-cn.com/problems/coin-lcci

给定数量不限的硬币，币值为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

[guodongxiaren]

动态规划题：

class Solution {
public:
    int waysToChange(int n) {
        const int N = 1000000;
        const int mod = 1000000007;
        int coins[4] = {1, 5, 10, 25};
        int dp[N+1] = {1};

        for (int i = 0; i < 4; ++i) {
            for (int j = coins[i]; j <= n; j++) {
                dp[j] = (dp[j] + dp[j-coins[i]]) % mod;
            }
        }
        return dp[n];
    }
};

数组初始化的时候，没有赋值的元素都会被初始化为0。但是不初始化就不会自动初始化为0。

[guodongxiaren]

动态规划题解：https://zhuanlan.zhihu.com/p/86010666