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 就是硬币的价值。  

#include <cstdio>
#include <cstdlib>
#include <cstring>
const int MAX = 32768+10;
long long d[MAX];
void solve() {
  int n, i, j;
  while (~scanf("%d", &n)) {
    memset(d, 0, sizeof(d));
    d[0] = 1;
    for (i = 1; i <= 3; ++i) {
      for (j = i; j <= n; ++j) {
        d[j] += d[j-i];
      }
    }
    printf("%lld\n", d[n]);
  }
}
int main(void) {
  solve();
  return 0;
}

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