322. 零钱兑换

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

考点

  • 完全背包

思路

完全背包的裸题

二维：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int coinChange(vector<int>& coins, int amount) {
    int n = coins.size();
    // f[i][j]: 考虑前i个，和凑成j的硬币个数，取最小值
    int f[13][10005];
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
      int w = coins[i - 1];
      for (int j = 0; j <= amount; ++j) {
        f[i][j] = min(f[i][j], f[i - 1][j]);
        if (j >= w) f[i][j] = min(f[i][j], f[i][j - w] + 1);
      }
    }
    if (f[n][amount] == 0x3f3f3f3f) return -1;
    return f[n][amount];
  }
};

压缩成一维：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  int coinChange(vector<int>& coins, int amount) {
    int n = coins.size();
    // f[i][j]: 考虑前i个，和凑成j的硬币个数，取最小值
    int f[10005];
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= n; ++i) {
      int w = coins[i - 1];
      for (int j = w; j <= amount; ++j) {
        f[j] = min(f[j], f[j - w] + 1);
      }
    }
    if (f[amount] == 0x3f3f3f3f) return -1;
    return f[amount];
  }
};