问题 2197 --动态规划 - 换零钱

2197: 动态规划 - 换零钱

时间限制: 1 Sec  内存限制: 128 MB
提交: 136  解决: 82
[提交][状态][命题人:]

题目描述

N元钱换为零钱，有多少不同的换法？币值包括1 2 5分，1 2 5角，1 2 5 10 20 50 100元。
例如：5分钱换为零钱，有以下4种换法：
1、5个1分
2、1个2分3个1分
3、2个2分1个1分
4、1个5分
(由于结果可能会很大，输出Mod 10^9 + 7的结果)

输入

输入1个数N，N = 100表示1元钱。(1 <= N <= 100000)

输出

输出Mod 10^9 + 7的结果
样例输入
Copy
5
样例输出
Copy
4

提示

来源

xinjun 

[提交][状态]