518. 零钱兑换 II

发表于 分类于 阅读次数： Waline： 本文字数： 86 阅读时长 ≈ 1 分钟

考点

  • 完全背包

思路

完全背包的裸题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
 public:
  int change(int amount, vector<int>& coins) {
    int n = coins.size();
    // f[i][j]: 考虑前i个，和凑成j的种类数
    unsigned long long f[5005];
    memset(f, 0, sizeof(f));
    f[0]=1;
    for (int i = 1; i <= n; ++i) {
      int w = coins[i - 1];
      for (int j = w; j <= amount; ++j) {
        f[j] += f[j - w];
      }
    }
    return f[amount];
  }
};