#322

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Coin Change

Find the minimum number of coins needed to reach a target amount using dynamic programming state transitions efficiently.

array dynamic programming breadth first search

Problem Statement

Given an array of distinct coin denominations and a total amount, determine the smallest number of coins required to form that amount. You may use each coin infinitely many times. If no combination of coins can form the total, return -1.

Design an algorithm that efficiently computes the minimum coins using dynamic programming state transitions. Consider how intermediate states build up to the target amount, ensuring no redundant computations while handling edge cases such as zero amount or unreachable sums.

Examples

Example 1

Input: coins = [1,2,5], amount = 11

Output: 3

11 = 5 + 5 + 1

Example 2

Input: coins = [2], amount = 3

Output: -1

Example details omitted.

Example 3

Input: coins = [1], amount = 0

Output: 0

Example details omitted.

Constraints

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

Solution Approach

Dynamic Programming Array

Create an array dp of length amount+1 initialized with infinity, set dp[0] = 0. For each coin and for each sub-amount, update dp[sub] = min(dp[sub], dp[sub-coin]+1). Return dp[amount] or -1 if unreachable.

Breadth-First Search Level Traversal

Treat each reachable amount as a BFS node. Start from 0 and enqueue sums formed by adding each coin. Track levels to represent number of coins used. Stop when target amount is reached or queue is exhausted.

State Transition Optimization

Focus on incremental updates for each state to avoid redundant recalculations. Only process sub-amounts where dp[sub-coin] is valid. This ensures the algorithm efficiently finds the minimal coin count while respecting the state transition pattern.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity varies: DP approach is O(amount * n) where n is number of coins; BFS may also approach similar bounds. Space complexity is O(amount) for DP array or BFS visited set.

What Interviewers Usually Probe

Checks if candidate recognizes state transition DP pattern for minimal coin computation.
Looks for proper handling of edge cases like unreachable amounts or zero amount.
Observes whether BFS alternative is considered for level-based minimal coin counting.

Common Pitfalls or Variants

Common pitfalls

Failing to initialize DP array correctly leading to invalid minimum computations.
Ignoring unreachable sums, resulting in incorrect positive coin counts instead of -1.
Overcounting coins by revisiting states without pruning already processed amounts.

Follow-up variants

Compute minimum coins when coins have limited quantity instead of infinite supply.
Return all possible combinations of coins that sum to the target amount.
Determine the number of ways to make up the amount rather than the minimal coins.

FAQ

What is the most efficient approach for the Coin Change problem?

Dynamic programming using a state transition array is most efficient; BFS is also valid for small amounts to traverse levels.

Why do we use infinity in the DP array for Coin Change?

Infinity marks amounts that are initially unreachable, ensuring min comparisons update only valid states.

Can the BFS approach replace dynamic programming for Coin Change?

Yes, BFS can compute the minimal coins by level traversal, but DP is generally faster for large amounts.

How does state transition dynamic programming prevent redundant computations?

By updating each sub-amount only based on valid previous states, it avoids recalculating combinations already considered.

What edge cases should I check when solving Coin Change?

Test zero amount, amounts smaller than the smallest coin, and amounts that cannot be formed with given coins.

terminal

Solution

Solution 1: Dynamic Programming (Complete Knapsack)

We define $f[i][j]$ as the minimum number of coins needed to make up the amount $j$ using the first $i$ types of coins. Initially, $f[0][0] = 0$, and the values of other positions are all positive infinity.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        m, n = len(coins), amount
        f = [[inf] * (n + 1) for _ in range(m + 1)]
        f[0][0] = 0
        for i, x in enumerate(coins, 1):
            for j in range(n + 1):
                f[i][j] = f[i - 1][j]
                if j >= x:
                    f[i][j] = min(f[i][j], f[i][j - x] + 1)
        return -1 if f[m][n] >= inf else f[m][n]

Continue Practicing

#329 longest increasing path in a matrix #542 01 matrix #773 sliding puzzle