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

在一个国家仅有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;
}

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