hdu1398 Square Coins —

hdu1398 Square Coins ——DP

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1398

题目大意：

　　给一个数字，不大于300，求有多少种用完全平方数表示这个数字的方法

题目思路：

　　方法跟hdu1283一样一样的……只需要把那道题目的代码稍微改一下就可以过了

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <cstdlib>
 4 #include <cstring>
 5 const int MAX = 32768+10;
 6 long long d[MAX];
 7 void solve() {
 8   int n, i, j;
 9   while (~scanf("%d", &n) && n) {
10     memset(d, 0, sizeof(d));
11     d[0] = 1;
12     for (i = 1; i <= floor(sqrt(n)); ++i) {
13       for (j = i*i; j <= n; ++j) {
14         d[j] += d[j-i*i];
15       }
16     }
17     printf("%lld\n", d[n]);
18   }
19 }
20 int main(void) {
21   solve();
22   return 0;
23 }

因为题目的范围很小嘛，只有300。