本文共 2148 字，大约阅读时间需要 7 分钟。

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 29605 Accepted Submission(s): 10543

Problem Description

Suppose there are 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. We want to make changes with these coins for a given amount of money.

For example, if we have 11 cents, then we can make changes with one 10-cent coin and one 1-cent coin, or two 5-cent coins and one 1-cent coin, or one 5-cent coin and six 1-cent coins, or eleven 1-cent coins. So there are four ways of making changes for 11 cents with the above coins. Note that we count that there is one way of making change for zero cent.

Write a program to find the total number of different ways of making changes for any amount of money in cents. Your program should be able to handle up to 100 coins.

Input

The input file contains any number of lines, each one consisting of a number ( ≤250 ) for the amount of money in cents.

Output

For each input line, output a line containing the number of different ways of making changes with the above 5 types of coins.

Sample Input

11 26

Sample Output

4 13

Author

Lily

Source

浙江工业大学网络选拔赛

问题链接：

问题简述：给定5种币值（1, 5, 10, 25, 50），给定钱数m，计算硬币组成m的组合数 问题分析：     Coin Change模板题，也可以用暴力法来解，正解是用DP来实现。这个题算是二维0-1背包问题。     这个题跟参考链接的题应该是同一个题，不明白用那个题解代码提交为什么会WA。也许是HDU2069有限制条件：Your program should be able to handle up to 100 coins. 而UVA674的限制条件是：Your program should be able to handle up to 7489 cents. 程序说明：（略） 参考链接： 题记：限制条件不同，解体方法不同。

AC的C++语言程序如下：

/* HDU2069 Coin Change */#include 
   
    using namespace std;const int coins[] = {
   1, 5, 10, 25, 50};const int K = sizeof(coins) / sizeof(coins[0]);const int M = 250;const int C = 100;int dp[M + 1][C + 1];   // dp[m][c]:用m个硬币组成c值的个数void dodp(){
       memset(dp, 0, sizeof(dp));    dp[0][0] = 1;    for(int k = 0; k < K; k++)        for(int j = 1; j <= C; j++)            for(int i = coins[k]; i <= M; i++)                dp[i][j] += dp[i - coins[k]][j - 1];}int main(){
       dodp();    int m;    while(~scanf("%d", &m)) {
           int ans = 0;        for(int i = 0; i <= C; i++) ans += dp[m][i];        printf("%d\n", ans);    }    return 0;}
   

转载地址：https://tigerisland.blog.csdn.net/article/details/105702014 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！