interviewalgo
, , ,
Source
Edit
History

322. 零钱兑换

Introduction

Question：322. 零钱兑换

Analysis

这道题做的有点久，一直陷到自己的错误解法中，没有跳出来，导致一直超时。先大概提提之前错误的解法。

令 dp[i][a] 表示使用 coins[:i] 构成 amount 的最小硬币数。因此：

  • dp[][0] = 0
  • dp[0][] = -1
  • dp[i][a] = min_{0 <= j*coins[i-1] <= a}(j + dp[i-1][a - j*coins[i-1])

实现下来就会发现这是一个O(amount^2 * N)的算法，而amount的最大值又能到 10^4，所以超时也不奇怪。

由于陷到这个方法中太久了，所以瞄了一眼题解。

好的，正确的动态规划方程是这样的：

  • dp[a] = min_{i} (dp[a - c_i]) + 1
  • dp[0] = 0

完全想错方向了，所以这道题只需要用O(amount*N)的时间即可解决。

Implement

1
2
3
4
5
6
7
8
9
10
11
12
13
int coinChange(vector<int>& coins, int amount) {
    if (amount == 0) return 0;
    // F(a) = min_i {F(a - c_i)} + 1;
    vector<int> dp(amount + 1, amount + 1);
    sort(coins.begin(), coins.end());
    dp[0] = 0;
    for(int a = 1;a <= amount;a++) {
        for(int i = 0;i < coins.size() && coins[i] <= a;i++) {
            dp[a] = min(dp[a], dp[a - coins[i]] + 1);
        }
    }
    return dp[amount] == amount + 1 ? -1 : dp[amount];
}
  • 这里用amount + 1来作为最大值，这样可以避免判断-1。
  • 排序是为了可以更快的结束第二个循环，由于coins的最大长度才 12 ，所以基本没有开销。