基准时间限制：1 秒 空间限制：131072 KB 分值: 20 

 收藏

 关注

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的结果)

Input

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

Output

输出Mod 10^9 + 7的结果

Input示例

5

Output示例

4

【代码】：

#include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #define maxn 105#define maxm 50005#define INF 0x3f3f3f3f#define ll long long#define MOD 1000000007using namespace std;/*每件物品无穷多个!它的实际意义：依次取出可用硬币集合中的每一种硬币，例如当前取出的硬币为3元硬币，设val(i)为凑成i元的方法数，则val(i)自然要增加val(i-3)，因为3元硬币的存在，所有能凑成(i-3)元的方法都可通过增加一枚3元硬币而凑成i元。*/int w[13]={ 1,2,5,10,20,50,100,200,500,1000,2000,5000,10000};int v[7]={ 1,2,5,10,20,50};int d[110000];int main(){ int n,c; scanf("%d",&n); d[0]=1; for(int i=0;i<13;i++) for(int j=w[i];j<=n;j++) d[j]=(d[j]+d[j-w[i]])%MOD; printf("%d\n",d[n]);}/*dp[i][j]:1. 保持金额不变, 减少货币种数2. 保持货币种数,减少金额大小if(i>=j) dp[i][j] = dp[i][j-1] + dp[i-j][j]if(i
              
               <= N） 中 当coins[j]（ 1 <= j <= 13）（放进去 ＋ 不放进去）两种场景的和好比，coins[] = {1, 2, 5} dp[2]有两种方案, dp[2][0] = dp[1][0] = 1; dp[2][1] = dp[0][2](直接选择一枚2分硬币的结果) + dp[1][0](2个1分硬币的结果) = 2 dp[2][2] = 0 + dp[2][1] ＝ 2 （因为价值为5的硬币放不进去，所以只能选择不放）PS: MOD = (10^9 + 7) 每步的结果都要MOD一下 >.<*/