钱币兑换问题

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6296 Accepted Submission(s): 3640

Problem Description 在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。
Input 每行只有一个正整数N，N小于32768。
Output 对应每个输入，输出兑换方法数。

Sample Input

2934
12553

Sample Output

718831
13137761

状态转移方程：dp[i][j] = dp[i-1][j]+dp[1][j-(1~3)] (d[0][0] = 1);
代码：
#include 
   
    
#include 
    
      #define MAX 35000 int dp[MAX] ; int main() { int n; while(scanf("%d",&n) != EOF) { memset(dp,0,sizeof(int)*(n+10)) ; dp[0] = 1 ; for(int i = 1 ; i <= 3 ; ++i) { for(int j = i ; j <= n ; ++j) dp[j] = dp[j]+dp[j-i] ; } printf("%d\n",dp[n]) ; } return 0 ; }
    
   

呵呵，，再附送你们一个神代码(不是我写的)：
#include
   
    
int main()
{
    int n,sum,i;
    while(scanf("%d",&n)!=EOF)
    {
        int t=n/3+1;//3分的个数 
        sum=0;
        for(i=0;i
    
     
因为本题的钱币数只有1,2,3三种，所以令t=n/3，然后遍历一遍i从0到t，代表面值为三分的个数，然后用总价值减去三分硬币所代表的价值，用这个值除以2，得到的数就是每确定一个三分的数值后对应的2分的硬币的兑换总数。最后再加上全部为1分的情况，就是所求的解了。
     

     
下面的代码简直是碉堡了。

hdu 1284 钱币兑换问题 完全背包之方案总数~

钱币兑换问题

hdu 1284 钱币兑换问题完全背包之方案总数~