硬币劃分

連結：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;
}