题目分析：定义dp[i][j]是将前i种硬币放到价值为j的背包里的方法数....
状态转移方程：dp[i][j]=sum(dp[i-1][j],dp[i][j-i]).........................具体件背包九讲
初始化化：dp[i][0]=0, 价值为0的方法当然为1，就是什么都不放
#include<iostream>
#include<cstdio>
using namespace std;
__int64 dp[400000];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=1;i<=3;i++)
for(int j=i;j<=n;j++)//j=1 WA了一次
dp[j]=dp[j]+dp[j-i];
printf("%I64d\n",dp[n]);
}
system("pause");
return 0;
}