杭電 1284 錢幣兌換問題【完全背包求方案總數】

解題思路：因為對于完全背包的狀態轉移方程f[v]=max(f[v],f[v-c[i]]+w[i])已經記錄了所有背包組成的方案，只不過通常問的是求最大值，現在要求方案總數

即為 f[v]=sum(f[v],f[v-c[i]+w[i]]),

Problem Description

在一個國家僅有1分，2分，3分硬幣，將錢N兌換成硬幣有很多種兌法。請你編程序計算出共有多少種兌法。

Input

每行只有一個正整數N，N小于32768。

Output

對應每個輸入，輸出兌換方法數。

Sample Input

2934 12553

Sample Output

718831 13137761

#include<stdio.h>
#include<string.h>
long long  f[50000];
int a[4];
long long sum(long long a,long long b)
{return a+b;
}int main()
{int n,i,v;while(scanf("%d",&n)!=EOF){memset(f,0,sizeof(f));f[0]=1;a[1]=1;a[2]=2;a[3]=3;for(i=1;i<=3;i++){for(v=a[i];v<=n;v++)f[v]=sum(f[v],f[v-a[i]]);}printf("%I64d\n",f[n]);}    
}