硬币划分

链接：https://www.nowcoder.com/questionTerminal/f0605c09c4ab4b019bbfd6ef79130478?answerType=1&f=discussion

来源：牛客网

有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱(n <= 100000)，有多少中组合可以组成n分钱？

输入描述:

输入整数n.(1<=n<=100000)
      

输出描述:

输出组合数，答案对1e9+7取模。      

示例1

输入

13      

输出

16      

#include<iostream>
#include<cstdio>
using namespace std;
const long long mod = 1e9+7;
int main()
{
    int n;
    int dp[100050]={0};
    scanf("%d", &n);

    int a[]={1,2,5,10};
    dp[0]=1;
    for(int i = 0; i < 4; i++)///对每种硬币取法都进行计算
    {
        ///从a[i]开始是为了排除前面小面额硬币对当前的影响
        ///同时，防止数组越界
        for(int j = a[i]; j <= n; j++)
        {
            ///当前种类方式应该等于当前已有方式加上从上一轮得到的方式数
            dp[j] = (dp[j]+dp[j-a[i]])%mod;
        }
    }
    printf("%d\n", dp[n]);



    return 0;
}