hdu2069 Coin Change ——DP

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2069 题目大意： 　　给一个数字，用1, 5, 10， 25,  50 这五种硬币，最多用100枚，有多少种组合方式。 题目思路： 　　这道题和之前的题目不同，有了硬币个数的限制，所以需要加上一维表示硬币的个数就可以了。d[i][j]表示价值为 i 的最多用 j 枚硬币有多少中组合方式。很多人用母函数做，感觉DP做简单多了…… 参考博客：http://www.cnblogs.com/qiufeihai/archive/2012/09/11/2680840.html

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAX = 250+10;
int d[MAX][MAX], n, a[5] = {1, 5, 10, 25, 50};
void solve() {
  while (~scanf("%d", &n)) {
    int i, j, k;
    memset(d, 0, sizeof(d));
    d[0][0] = 1;
    for (k = 0; k < 5; ++k) {
      for (j = 1; j <= 100; ++j) {
        for (i = a[k]; i <= n; ++i) {
          d[i][j] += d[i-a[k]][j-1];
        }
      }
    }
    int sum(0);
    for (i = 0; i <= n; ++i) {
      sum += d[n][i];
    }
    printf("%d\n", sum);
  }
}
int main(void) {
  solve();
  return 0;
}

　　还有要注意一点，初始化要d[0][0] = 1 因为题目中说：Note that we count that there is one way of making change for zero cent. 只能初始化这个值，不要把所有的d[0][i]都初始化为1了……因为这显然就把结果增加了。。这是因为从 d[0][0] 可以推算出后面的d[0][1,,,,100]