322. Coin Change

Problem

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

https://leetcode.com/problems/coin-change/

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

Constraints:

1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4

Test Cases

1 2	class Solution: def coinChange(self, coins: List[int], amount: int) -> int:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('coins, amount, expected', [
    ([1,2,5], 11, 3),
    ([2], 3, -1),
    ([1], 0, 0),

    ([1,2,4,5], 12, 3),
    ([1,60,100], 120, 2),

    ([186,419,83,408], 6249, 20),
    ([411,412,413,414,415,416,417,418,419,420,421,422], 9864, 24),
    ([2147483647], 2, -1),
])
class Test:
    def test_solution(self, coins, amount, expected):
        sol = Solution()
        assert sol.coinChange(coins, amount) == expected

Thoughts

任取一种硬币 i，如果金额 amount - coins[i] 可以由最少 m 枚硬币组合而成，那么给这堆硬币再增加一枚硬币 i（共 m + 1 枚），就可以组合出金额 amount。所有可能的组合方式中，取最小的那个就是所求的值。而如果找不到这样的组合，就说明金额 amount 无法由 coins 组合出来。

记组合出金额 a 的最少硬币数量为 mc[a]，有（其中 ∞ 表示组合不出来）：

mc[a]=\begin{cases} 0 & \text{if }a=0 \\ \infty & \text{if }0<a<\min_i\{coins[i]\} \\ 1+\min_i\{mc[a-coins[i]]\mid coins[i]\le a\} & \text{otherwise} \\ \end{cases}

这样从 mc[0] 开始一直推算到 mc[amount] 即可。最后如果 mc[amount] = ∞，按要求返回 -1 即可（实践中可以用 amount + 1 替代 ∞，只要结果大于 amount 就是组合不出来的意思）。

时间复杂度是 O(amount * C)（C 是不同面值的硬币种类数量），空间复杂度是 O(amount)。

可以发现在计算 mc[a] 的时候，最多只会用到 $a-c_{max}$ 及之后的值（其中 $c_{max}=\max_i\{coins[i]\}$ 即硬币的最大面值）。所以保存 mc 中间结果的时候，只需要始终保留最新的 $c_{max}$ 个值即可，空间复杂度为 $O(c_{max})$ 。

Code

solution.py

class ForgetfulList:
    def __init__(self, limit: int, default: int = None, cnt: int = 0):
        """Inits a forgetful list which can remember at most `limit` recent values.
        The first `cnt` values will be set to `default`.
        """
        self._limit = limit
        self._buffer = [default] * limit
        self._pos = cnt % self._limit

    def __getitem__(self, idx: int) -> int:
        return self._buffer[idx % self._limit]

    def __setitem__(self, idx: int, val: int):
        self._buffer[idx % self._limit] = val

    def append(self, val: int):
        self._buffer[self._pos] = val
        self._pos = (self._pos + 1) % self._limit


class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        if amount == 0:
            return 0

        coins = [val for val in coins if val <= amount] # To avoid coin assassins (huge-value coins).
        if not coins:
            return -1

        min_val = max_val = coins[0]
        for val in coins:
            if val > max_val:
                max_val = val
            elif val < min_val:
                min_val = val

        mc = ForgetfulList(max_val, amount + 1, min_val)
        mc[0] = 0
        for amt in range(min_val, amount + 1):
            mc.append(min(mc[amt - val] + 1 for val in coins if amt >= val))

        return -1 if mc[amount] > amount else mc[amount]

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。