hdu——1284——钱币兑换问题

本文主要是介绍hdu——1284——钱币兑换问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem Description
在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。
 


Input
每行只有一个正整数N，N小于32768。
 


Output
对应每个输入，输出兑换方法数。
 


Sample Input
2934
12553
 


Sample Output
718831

13137761

纯数学：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{int n;while(cin>>n){int s;s=n/3+1;//求出最多可容纳3的个数for(int i=0;i<=n/3;i++){s+=(n-3*i)/2;//除去3，最多可容纳2的个数}cout<<s<<endl;}return 0;
}

 完全背包：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{int n;int dp[35000];while(cin>>n){memset(dp,0,sizeof(dp));dp[0]=1;for(int i=1;i<=3;i++){for(int j=i;j<=35000;j++){dp[j]+=dp[j-i];}}cout<<dp[n]<<endl;}return 0;
}

这篇关于hdu——1284——钱币兑换问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---