Coin Change HDU - 2069 （超详细题解）

迈不过友情╰ 2021-08-28 11:54 272阅读 0赞

### 文章目录 ###

*   *  1.题目
     *  2.题意
     *  3.解题思路
     *  4.代码

## 1.题目 ##

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

## 2.题意 ##

给你五种硬币：1,5,10,25,50，现在给出一个n，求出用这些硬币组成价值为n的方法数。

## 3.解题思路 ##

完全背包问题，状态转移方程dp\[k\]\[v\] = dp\[k\]\[v\]+dp\[k - 1\]\[v - a\[i\]\]，其中dp\[k\]\[v\]表示用k个硬币凑成价值为v的方法数,a\[i\]表示硬币i的价值。

背包九讲: [点击这里][Link 1].

## 4.代码 ##

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    int a[5] = {  1,5,10,25,50 }; ///表示5种硬币各自的价值 
    int dp[110][260];///表示dp[i][v] 用i个硬币凑成价值为v的方法数 
    int main()
    { 
    	int n;
    	while (cin >> n)
    	{ 
    		memset(dp, 0, sizeof(dp)); //初始化dp数组
    		dp[0][0] = 1;///边界
    		for (int i = 0; i < 5; i++)
    		{ 
    			for (int k = 1; k <= 100; k++) //k个硬币
    			{ 
    				for (int v = a[i]; v <= n; v++)
    				{ 
    					dp[k][v] += dp[k - 1][v - a[i]];//状态转移方程
    				}                        
    			}
    		}
    		int ans = 0;
    		for (int i = 0; i <= 100; i++)
    		{ 
    			ans += dp[i][n];
    		}
    		cout << ans << endl;
    	}
    	return 0;
    }

参考博客链接：  
[点击这里][Link 2].

[Link 1]: https://blog.csdn.net/yandaoqiusheng/article/details/84782655
[Link 2]: https://blog.csdn.net/u012435889/article/details/42563151/