hdu 1284 錢幣兌換問題 完全背包之方案總數~

錢幣兌換問題

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分的情況，就是所求的解了。

下面的代碼簡直是碉堡了。