题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1398

背包的硬币问题

代码

#include<stdio.h>
#include<string.h>

int main(void)
{
int i,j,k,n;
int dp[310];
int a[20];
for(i=1;i<=17;i++)
a[i]=i*i;
memset(dp,0,sizeof(dp));
dp[0]=1;
for(i=1;i<=17;i++)
{
for(j=a[i];j<=300;j++)
{
dp[j]=dp[j]+dp[j-a[i]];
}
}
while(scanf("%d",&n)==1&&n)
{
printf("%d\n",dp[n]);
}
return 0;
}

HDU-1398-Square Coins