hdu1284 钱币兑换问题 —

hdu1284 钱币兑换问题 ——DP

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

题目大意：

　　中文题……

题目思路：

　　只有3个硬币，范围是32768，可以一个一个枚举硬币，如果只放价值为1的硬币，从d[1]递推到d[n]；如果再加上价值为2的硬币，那么就从d[2]递推到d[n]；在加上价值为3的硬币，就从d[3]递推到d[n].递推公式是d[j] = d[j] + d[j-i]； d[j]表示j有几种只用1，2, 3这三个数字的拆分方法，i 就是硬币的价值。

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

参考博客：http://www.cnblogs.com/qiufeihai/archive/2012/09/11/2680840.html