HDUOJ 1284 钱币兑换问题

题目链接

Problem Description

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

Input

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

Output

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

Sample Input

2934 12553

Sample Output

718831 13137761

完全背包求方案数，套个板子即可，AC代码如下：

#include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ int m; while(~scanf("%d",&m)){ int dp[m+1]={0},p[3]={1,2,3},ans=0; dp[0]=1; for(int i=0;i<3;i++){ for(int j=p[i];j<=m;j++){ dp[j]+=dp[j-p[i]]; } } printf("%d\n",dp[m]); } }