HDU-1284:钱币兑换问题 推理+动态规划（dp）

文章目录

题目大意： 题目链接 HDU 1284(点击可进入网页提交)

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

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

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

思路：

方法1：

在看到题目后，我们可以很自然地（请原谅我用如此恶劣的词）想到暴力枚举，那么问题来了，该如何枚举呢？其实我们仔细想一下就可以发现对于每一种硬币的个数来说，它所出现次数一定是一个区间。
如何理解这句话呢？我们以3分的硬币的个数为例，它在所有的排列组合中，所出现的最少次数一定是0，即将钱n全部分成1分和2分的硬币，不包含3分硬币，这是一种合理的方案；好了，那么它最大次数，也可以很快算出为 n/3 (向下取整)，既然最大为 n/3,那么小于等于n/3的个数也能出现，所以3分硬币所出现个数 cnt1 的区间为 0<=cnt1<=n/3。

分完了3分硬币，还剩下的钱为 n-3cnt,那么接下来我们考虑2分硬币，同样的思考方式，2分硬币的最小个数为0，最大个数为 （n-3cnt1)/2 ； 所以2分硬币出现个数cnt2的区间为 0<=cnt2<=(n-3*cnt1)/2。

3分硬币和2分硬币都分完了，剩下的都是1分硬币了，数量是可以确定的，所以不用考虑了。

所以我们可以用一层循环来枚举3分硬币的个数，然后用变量ans加上2分硬币的个数，循环完所得到的ans就是答案。

说了这么多，其实它的代码是非常简单的。

int ans=0;//用来记录答案for(int cnt1=0;cnt1<=n/3;cnt1++){ans+=(n-3*cnt1)/2+1; //即0到（n-3*cnt1）/2 的个数为 （n-3*cnt1）/2+1;}//得到的ans为答案

贴一发AC代码：

#include <iostream>#include <cstdio>using namespace std;int main(){    int n;    while(cin>>n)    { int ans=0;//用来记录答案 for(int cnt1=0;cnt1<=n/3;cnt1++) {     ans+=(n-3*cnt1)/2+1;//即0到（n-3*cnt1）/2 的个数为 （n-3*cnt1）/2+1; } if(n==1)     ans=1; if(n==2)     ans=2; cout<<ans<<endl;    }    return 0;}

方法2：
动态规划（dp）
因为有三种硬币，所以我们可以刷新三次dp数组，变量i表示几分硬币，变量j表示钱；所以可以写出递推方程为 dp[j]+=dp[j-i];

AC代码如下：

#include <iostream>#include <cstdio>using namespace std;int dp[35000];void solve(){    dp[0]=1;    for(int i=1;i<=3;i++) //三次刷新    { for(int j=i;j<32768;j++) {     dp[j]+=dp[j-i]; }    }}int main(){    int n;    solve();    while(cin>>n)    { cout<<dp[n]<<endl;    }    return 0;}

希望通过本篇博客你能有所收获！加油！