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

钱币兑换问题

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 10272    Accepted Submission(s): 6253 Problem Description 在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。   Input 每行只有一个正整数N，N小于32768。   Output 对应每个输入，输出兑换方法数。   Sample Input 2934 12553   Sample Output 718831 13137761   Author SmallBeer(CML)   Source 杭电ACM集训队训练赛（VII）   Recommend lcy   Statistic |  Submit |  Discuss |  Note

解析：懵逼啊，明明会多重背包，为什么比赛时想不起来，知道是DP一直不知道找状态方程，还是自己太菜

代码：

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<vector> #include<queue> #include<map> #include<cmath> #define N 50009 using namespace std; const int INF = 0x3f3f3f3f; int dp[N]; void init() { memset(dp, 0, sizeof(dp)); dp[0] = 1; // fanganshu for(int i = 1; i <= 3; i++) { for(int j = i; j <= 33000; j++) dp[j] += dp[j - i]; } } int main() { init(); int n; while(~scanf("%d", &n)) printf("%d\n", dp[n]); return 0; }