hdu 1284 钱币兑换【完全背包问题】

题目大意，给你1分、2分、3分的硬币，问你组成n分的钱有多少种兑换方法

这个题就是一个不带价值的完全背包问题，由于和完全背包问题的模型还是有一点差距，那么我们来讲讲如何把它作为一个完全背包问题来分析。首先这个题， 1,2,3分的硬币数量是无限的，那么对于 总量为j的硬币来说，他可以取k1个1分的，k2个2分的和k3个3分的，这就具备了完全背包的基本雏形，我们很容易想到，如果只有1分的，显然只有一种做法，然后我们增加两分的，此时，我们的容量，可能是原来全部一分的，加上这一次我把其中一个两分的加进去，每次都加进去一个两分的，这样就可以把所有的两分的情况都加上去。
由此我们得到的状态转移方程
dp[i][j]=dp[i-1][j]+dp[i][j-i]
i表示目前选的几分的硬币，j表示当前的容量，也就是说，当我加入i分的硬币的时候，对于容量j来说，他可能全部是只有i-1分的情况，可以能是我再添加一个i分的情况。
代码如下：

#include <bits/stdc++.h>
using namespace std;
int dp[4][35000];
int main()
{
    memset(dp,0,sizeof(dp));
    for(int i=0;i<35000;i++)
    {
        dp[1][i]=1;
    }
    for(int i=2;i<=3;i++)
    {
        for(int j=0;j<35000;j++)
        {
           if(j>=i) dp[i][j]=dp[i-1][j]+dp[i][j-i];
            else dp[i][j]=dp[i-1][j];
        }
    }
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        printf("%d\n",dp[3][n]);
    }
    return 0;
}