[数据结构与算法]LeetCode 面试题 08.11. 硬币 --完全背包

面试题 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

题解

完全背包问题，和这个题目一模一样LeetCode 518. 零钱兑换 II–动态规划–完全背包

AC代码

class Solution {
public:
    int coins[4]={1,5,10,25};
    int dp[1000010];
    int waysToChange(int n) {
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        for(int i=0;i<4;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(j>=coins[i])
                dp[j]+=dp[j-coins[i]];
                dp[j]%=1000000007;
            }
        }
        return dp[n];
    }
};