零钱兑换

题意

给定硬币面额和金额，求最少硬币数。每种硬币无限使用。

思路

dp[i] 表示凑成金额 i 的最少硬币数。dp[i] = min(dp[i-c] + 1) 对所有 c <= i。初值 dp[0] = 0，其余 amount + 1（不可达哨兵）。最终 dp[amount] > amount 则无解。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int coinChange(vector<int> &coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++)
            for (int c : coins)
                if (i >= c)
                    dp[i] = min(dp[i], dp[i - c] + 1);
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, amt;
    cin >> n >> amt;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    cout << Solution().coinChange(a, amt) << '\n';
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23#!/usr/bin/env python3
from typing import List


class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [amount + 1] * (amount + 1)
        dp[0] = 0
        for i in range(1, amount + 1):
            for c in coins:
                if i >= c:
                    dp[i] = min(dp[i], dp[i - c] + 1)
        return -1 if dp[amount] > amount else dp[amount]


def main():
    n, amt = map(int, input().split())
    a = list(map(int, input().split()))
    print(Solution().coinChange(a, amt))


if __name__ == "__main__":
    main()

复杂度

时间复杂度： $O(n \cdot \text{amount})$ 。
空间复杂度： $O(\text{amount})$ 。

总结

零钱兑换是完全背包求最少物品数的经典题。不可达哨兵用 amount + 1（而非 INF），因为最多用 amount 个 1 元硬币。

目录

题意

思路

代码

复杂度

总结