322. Coin Change Medium

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.

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

Approach

Input: An integer array coins, an integer amount

Output: Return the fewest number of coins to make up amount, or -1 if it cannot be made up.

This problem belongs to Complete Knapsack + Counting DP problems.

This problem has multiple solutions:

1. Memoized Recursion (DFS + Cache)
2. 1D DP

Solution 1: Memoized Search (Recursion + Cache)

Idea:

• Function dfs(amount) represents: the minimum number of coins needed to make up amount.
• For each coin coin, try to solve for amount - coin recursively.
• Use memo dictionary to remember calculated results.

Solution 2: 1D DP

State Definition:

• dp[i] represents the minimum number of coins needed to make up amount i.

Transition Equation:

• dp[i] = min(dp[i], dp[i - coin] + 1), where coin iterates over all usable coins in coins.

Initialization:

• dp[0] = 0 (0 coins needed for amount 0).
• Other dp[i] = inf representing initially impossible to make up.

Implementation

Solution 1: Memoized Search (Recursion + Cache)

python

from typing import List
from functools import cache

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        n = len(coins)

        # Use cache to accelerate recursion, preventing redundant calculation
        @cache
        def dfs(i: int, c: int) -> int:
            # If no coins available
            if i < 0:
                return 0 if c == 0 else float('inf')  # 0 coins needed for 0 amount, otherwise impossible
            
            if c < 0:
                return float('inf')  # Amount going negative means invalid search, return infinity
            
            # Skip current coin OR choose current coin (dfs(i, c - coins[i]) means current coin can be reused)
            return min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1)

        # Attempt to make up amount starting from the last coin
        ans = dfs(n - 1, amount)
        return ans if ans != float('inf') else -1  # If target amount cannot be made, return -1

javascript

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    const cache = new Map();
    function dfs(i, c) {
        if (i < 0) 
            return c == 0 ? 0 : Infinity;

        if (cache.get(`(${i}, ${c})`))
            return cache.get(`(${i}, ${c})`);

        let ans;
        if (c < coins[i])
            ans = dfs(i - 1, c)
        else {
            ans = Math.min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1)
        }

        cache.set(`(${i}, ${c})`, ans);
        
        return ans;
    }

    const ans = dfs(coins.length - 1, amount);
    return ans < Infinity ? ans : -1;
};

Solution 2: 1D DP

python

from typing import List

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        n = len(coins)

        # Initialize dp array, f[c] represents minimum coins needed for amount c
        # Initial values all set to infinity, implying cannot be made up initially
        f = [float('inf')] * (amount + 1)

        # 0 coins needed to make up 0 amount
        f[0] = 0

        # Traverse every coin denomination
        for x in coins:
            # Update all amounts >= x
            for c in range(x, amount + 1):
                # State transition: Choose current coin x or not
                # If chosen, f[c] can transition from f[c - x] + 1
                f[c] = min(f[c], f[c - x] + 1)

        ans = f[amount]

        # If f[amount] remains infinity, target amount cannot be made. Return -1
        return ans if ans < float('inf') else -1

javascript

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;

    for (let x of coins) {
        for (let c = x; c < amount + 1; c++) {
            dp[c] = Math.min(dp[c], dp[c - x] + 1);
        }
    }
    const ans = dp[amount];
    return ans < Infinity ? ans : -1;
};

Complexity Analysis

• Time Complexity: O(amount * n)
• Space Complexity:
  • Memoized Recursion (Recursion + Cache): O(amount * n)
  • 1D DP: O(amount)

Links

322. Coin Change (English)

322. 零钱兑换 (Chinese)