链接：https://ac.nowcoder.com/acm/contest/910/B 来源：牛客网
兑换零钱
时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld
题目描述
现有N元钱，兑换成小额的零钱，有多少种换法？币值包括1 2 5分，1 2 5角，1 2 5 10 20 50 100元。 (由于结果可能会很大，输出Mod 10^9 + 7的结果)
输入
输入描述:
第一行输入一个整数T，代表有T组数据
接下来T行，每行输入1个数N，N = 100表示1元钱。(1 <= N <= 100000)
输出描述:
输出Mod 10^9 + 7的结果
示例1
输入
复制
2
5
4
输出
复制
4
3
备注:
5分钱兑换为零钱，有以下4种换法：
1、5个1分
2、1个2分3个1分
3、2个2分1个1分
4、1个5分
#include<bits/stdc++.h>
const int mod = 1e9+7;
using namespace std;
int p[15] = {1,2,5,10,20,50,100,200,500,1000,2000,5000,10000};
int dp[100005];
int main() {
memset(dp, 0, sizeof(dp));
dp[0]=1;
for (int i = 0; i < 13; i++) {
for (int j = p[i]; j < 100000; j++)
dp[j] = (dp[j] + dp[j-p[i]]) % mod;
}
int t;
scanf("%d", &t);
int n;
while (t--) {
scanf("%d", &n);
printf("%d\n", dp[n]);
}
return 0;
}
