题解报告：hdu 1284 钱币兑换问题（简单数学orDP）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1284

Problem Description

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

Input

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

Output

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

Sample Input

2934

12553

Sample Output

718831

13137761

解题思路：这道题可以当做数学题来做。假设某种方案要使用i枚3分硬币（i∈[0,n/3]），那么剩下的就有n-3*i分需要用2分和1分补全。对于2分硬币的个数，可能使用0，1，·····（n-3*i）/2枚，剩下的全都用1分硬币即可。也就是说当使用i枚3分硬币时，就会产生出{（n-3*i）/2+1}*1=（n-3*i）/2+1种方案，那么只要枚举i，将所有方案数相加即可。

AC代码一：

 #include<bits/stdc++.h>

 using namespace std;

 int main(){

     int sum,n;

     while(cin>>n){

         sum=;

         for(int i=;i*<=n;++i)

             sum+=(n-i*)/+;

         cout<<sum<<endl;

     }

     return ;

 }

AC代码二：考虑dp，dp[j]表示用若干个硬币组成钱j的方案数，易得状态转移方程为：dp[j]+=dp[j-i]（j>=i），意思是当前币值是i，那么在组成钱j的基础上还可以这样增加新的方案数：用之前的j-i分再和当前i分组成钱j即增加了dp[j-i]*1这么多的方案数。举个栗子：现将3分钱兑换成硬币的所有方案数有①1+1+1=3--->1种;②去掉2枚1分换成1枚2分的硬币1+2=3，那么增加了之前的1种方案数，现共有2种方案数(dp[3]+=dp[3-2])；③还有一种就是用1枚3分的硬币替换3枚1分的硬币3+0=3，定义组成0钱的方案数为1种，那么此时也增加1种方案数(dp[3]+=dp[3-3])，所以组成3分钱共有3种方案数。注意：初始化dp数组全为0，定义dp[0]=1，因为组成钱0（事实上钱0是由钱i-i=0即i=i这种情况得来的）也算一种方案数，然后对于每种币值，从i～最大35000枚举更新累加对应组成钱j的方案数即可。

 #include<bits/stdc++.h>

 using namespace std;

 int main(){

     int n,dp[]={};

     for(int i=;i<=;++i)//币值

         for(int j=i;j<;++j)//钱j，每种硬币可以有无限个-->完全背包

             dp[j]+=dp[j-i];

     while(cin>>n){cout<<dp[n]<<endl;}

     return ;

 }

AC代码三(936ms)：用母函数做有点危险了-->差点TLE=_=||，还是贴一下代码吧233！

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=;

 int n,c1[maxn],c2[maxn];

 void init(){

     memset(c1,,sizeof(c1));

     memset(c2,,sizeof(c2));

     c1[]=;

     for(int i=;i<=;++i){

         for(int j=;j<maxn;++j)

             for(int k=;j+k<maxn;k+=i)

                 c2[j+k]+=c1[j];

         for(int j=;j<maxn;++j)

             c1[j]=c2[j],c2[j]=;

     }

 }

 int main(){

     init();

     while(~scanf("%d",&n)){

         printf("%d\n",c1[n]);

     }

     return ;

 }

秒客网