题目链接：

题目就是一个数学化简题，不是很难，

一般会想到利用三个循环，直接暴力，这样答案是正确的，但很明显会超时，所以要想办法将其循环层数减少。

i+2*j+3*k==n

可以化为（n-3*k）/2;

这样就减少了两层循环了

看我的代码

#include<stdio.h>

int main(void)

{

int n,s;

int i,j,k;

while(scanf("%d",&n)==1)

{

s=0;

k=n/3;

for(i=0;i<=k;i++)

{

s=s+(n-i*3)/2+1;

}

printf("%d\n",s);

}

return 0;

}

 

 

我们用dp[n]表示用这些硬币组成n的方法总数。。。。

 

然后随着硬币种类的增加来更新dp[]的值，也就是最外面的一层循环for(i :1-->3)开始初始化的时候没有硬币，然后新来了面值为1的硬币，接着又来了面值为2的硬币。。。。

 

显然，每新增加一种面值的硬币，dp[]的值一定在增加。。。新的dp[] = 未新增前的dp[] + dp[1件新增硬币] +  dp[2件新增硬币] + dp[3件新增硬币] +.......

dp[k件新增硬币]

 

由于for里用了完全背包里的顺序，for(j = c[i]; j <= n; j++)，所以dp[j] += dp[j - c[i]];中的dp[j - c[i]]已经是有k件新增硬币的状态了。。。。。

即j不停地向右，开始的时候得到只有一个新增硬币而组成n的总数，然后由只有1个新增硬币的结果得到只有2个新增硬币而组成n的总数，慢慢地,。。。。得到由越来越多件新增硬币组成n的总数得到的dp[i]就是该容量下的总数了

dp代码

#include<stdio.h>

#include<string.h>

int main(void)

{

int i,j,k,n;

int dp[32769];

while(scanf("%d",&n)==1)

{

memset(dp,0,sizeof(dp));

dp[0]=1;

for(i=1;i<=3;i++)

{

for(j=i;j<=n;j++)

dp[j]=dp[j]+dp[j-i];

}

printf("%d\n",dp[n]);

}

return 0;

}

 

dp代码

#include<stdio.h>

#include<string.h>

int main(void)

{

int dp[32769];

int i,j,k,n;

memset(dp,0,sizeof(dp));

dp[0]=1;

for(i=1;i<=3;i++)

{

for(j=i;j<=32768;j++)

{

dp[j]=dp[j]+dp[j-i];

}

}

while(scanf("%d",&n)==1)

{

printf("%d\n",dp[n]);

}

return 0;

}