钱币兑换问题 hdu 1284

钱币兑换问题 hdu 1284"/>

钱币兑换问题 hdu 1284

题源：钱币兑换问题 hdu 1284
题目：
在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。
Input
每行只有一个正整数N，N小于32768。
Output
对应每个输入，输出兑换方法数。
Sample Input
2934
12553
Sample Output
718831
13137761

思路：
先把这个数除以3，看能分成多少个3，然后循环依次减去i个3，用差除以2，得到的数就是当由i个3组成时剩下的由1和2组成的方案数（有几个2就有几种方案，例如有50个2依次用两个1代替2，则由50种方案）
AC代码：

#include<bits/stdc++.h>
#include<cmath>
typedef long long ll;
using namespace std;
//int a[100][100];
int a,b;
int main()
{while(cin>>a){ll t=a/3+1,sum=0;//因为如果全为1组成也是一种方案，则t要加1；for(int i=0;i<=a/3;i++){sum+=(a-i*3)/2;//减去i个3后能被几个2组成；}t+=sum;cout <<t<<endl;}return 0;}

这两天学了背包和记忆化搜索，感觉这一题有了新的不同的做法；
首先 这一天完全属于完全背包问题；
本题限制条件是: 金钱总数<=N.

本题目标条件是: 求构造方法数目.
令dp[i][j]==x 表示用前i种硬币构造j 美分共有x种方法.
初始化: dp为全0且dp[0][0]==1.
状态转移: dp[i][j] = sum( dp[i-1][j] , dp[i][j-val[i]])
Sum是求和, val[i]是第i种硬币的面值. 上述方程 前者是指第i值硬币一个都不选, 后者是指至少选1个第i种硬币.
AC代码：

#include<bits/stdc++.h>
#include<cmath>
typedef long long ll;
using namespace std;
ll dp[40000];
int main()
{int sum;while(cin>>sum){memset(dp,0,sizeof dp);dp[0]=1;//当钱是0元时，也是一种兑换方法；for(int i=1;i<=3;i++)for(int j=i;j<=sum;j++)dp[j]=dp[j]+dp[j-i];cout <<dp[sum]<<endl;}return 0;}

另外这道题应该还可以用记忆化搜索，等有时间再更新吧