Input: coins = [1, 2, 3], target = 5
Output: 2

Input: coins = [2, 4], target = 5
Output: -1

In Plain English

New to this one? Start here. Below is the core idea in everyday language, plus a real-world analogy—then the sections that follow build on it with the formal reasoning, code, and step-by-step walkthroughs.

Intuition - Top-Down

In this problem, there’s no restriction on the number of coins we can use, which makes a brute force approach that tries every possible coin combination impossible, due to the infinite number of possible combinations. This indicates the need for a more efficient method.

Consider the example below:

If we use a 3-dollar coin from the array, then we’ll only need 2 dollars more to make 5. This gives us a new target: find the fewest number of coins needed to make 2 dollars:

This indicates we’ve identified subproblems within the main problem, where each subproblem requires finding the fewest number of coins needed to make a smaller target.

Each coin we use creates a new subproblem. For example, using a 1-dollar coin changes our target from 5 to 4 dollars. Let's visualize how these smaller targets, representing new subproblems, are created after using each coin:

In extension, each of these subproblems can be solved by breaking them down into further subproblems:

A path that ends with a target of 0 means the coins used in that path add up to 5. If the target becomes negative, it means the path is invalid, so we should stop extending the path.

We’ve observed how new subproblems are created, but haven’t yet addressed how to attain the solutions to them. Remember, each subproblem needs to return the minimum number of coins needed to reach its target.

Consider the main problem with a target of 5. To solve this, we first need to find the minimum number of coins needed to reach each of its three subproblems. The solution to the main problem is the smallest result among these subproblems, plus 1, to account for the coin used to create the subproblem. This highlights an optimal substructure in the problem, allowing us to define the following recurrence relation:

min_coin_combination(target) = 1 + min(min_coin_combination(target - coin_i) | coin_i ∈ coins)

Base case
Naturally, we need a base case for this formula. The base case occurs when the target equals 0, which is the simplest version of this problem, as no coins are needed to meet the target. In this case, we return 0.

Memoization
An important thing to notice is that we might end up solving the same subproblem multiple times. For instance, we calculate the subproblem target = 3 two times in the previous example:

This highlights the existence of overlapping subproblems. Memoization improves our solution by storing the solutions to subproblems as they are computed, ensuring each subproblem is solved only once. This eliminates redundant calculations, and can significantly reduce the size of the recursion tree:

Implementation - Top-Down**

def min_coin_combination_top_down(coins: List[int], target: int) -> int:
    res = top_down_dp(coins, target, {})
    return -1 if res == float('inf') else res
    
def top_down_dp(coins: List[int], target: int, memo: Dict[int, int]) -> int:
    # Base case: if the target is 0, then 0 coins are needed to reach it.
    if target == 0:
        return 0
    if target in memo:
        return memo[target]
    # Initialize 'min_coins' to a large number.
    min_coins = float('inf')
    for coin in coins:
        # Avoid negative targets.
        if coin <= target:
            # Calculate the minimum number of coins needed if we use the current coin.
            min_coins = min(min_coins, 1 + top_down_dp(coins, target - coin, memo))
    memo[target] = min_coins
    return memo[target]

#include <vector>
using namespace std;

const int INF = 1000000000;             // stands in for "impossible"

int minCoinsFrom(vector<int>& coins, int target) {
    if (target == 0) {                  // base case: 0 coins make 0
        return 0;
    }
    int best = INF;
    for (int i = 0; i < (int)coins.size(); i++) {
        if (coins[i] <= target) {       // this coin fits
            int sub = minCoinsFrom(coins, target - coins[i]);
            if (sub != INF && sub + 1 < best) {   // using this coin is better
                best = sub + 1;
            }
        }
    }
    return best;
}

int minCoinCombinationTopDown(vector<int>& coins, int target) {
    int result = minCoinsFrom(coins, target);
    return result == INF ? -1 : result;
}

// These methods live inside a class, e.g. class Solution { ... }
static final int INF = 1000000000;      // stands in for "impossible"

int minCoinCombinationTopDown(int[] coins, int target) {
    int result = minCoinsFrom(coins, target);
    return result == INF ? -1 : result;
}

int minCoinsFrom(int[] coins, int target) {
    if (target == 0) {                  // base case: 0 coins make 0
        return 0;
    }
    int best = INF;
    for (int i = 0; i < coins.length; i++) {
        if (coins[i] <= target) {       // this coin fits
            int sub = minCoinsFrom(coins, target - coins[i]);
            if (sub != INF && sub + 1 < best) {   // using this coin is better
                best = sub + 1;
            }
        }
    }
    return best;
}

Complexity Analysis

Time complexity:

• Without memoization, the time complexity of min_coin_combination_top_down would be $O(n^{target/m})$, where $n$ denotes the number of coins, and $m$ denotes the smallest coin value. The recursion tree has a branch factor of $n$ because we make a recursive call for up to $n$ coins. The depth of the tree is $target/m$ because in the worst case, we continually reduce the target value by the smallest coin.

• With memoization, each subproblem is solved only once. Since there are at most $target$ subproblems, and we iterate through all $n$ coins for each subproblem, the time complexity is $O(target\cdot n)$.

Space complexity: The space complexity is $O(target)$ because, while the maximum depth of the recursive call stack is only $target/m$, the memoization array stores up to $target$ key-value pairs.

Intuition - Bottom-Up

Using the same technique discussed in the Climbing Stairs problem, we can convert our top-down solution to a bottom-up one by translating the memoization array to a DP array.

First, let’s look at the value our memoization array stores, as shown in the following code snippet of the top-down implementation:

for coin in coins:
    if coin <= target:
        min_coins = min(min_coins, 1 + top_down_dp(coins, target - coin, memo))
memo[target] = min_coins

Translating this to a DP array provides the following code:

for coin in coins:
    if coin <= target:
        dp[target] = min(dp[target], 1 + dp[target - coin])

This code snippet only includes the calculation for one target value. In our top-down solution, this calculation is repeated for every target value from the initial target, down to the base case (target == 0).

In the bottom-up solution, we need to reverse this order by starting with the base case and working our way up to the initial target value (hence the name “bottom-up”). This is necessary because our DP array calculation depends on the DP values of smaller targets. So, we need to calculate the answers for smaller targets first. This can be done using a for-loop from 1 to the target (starting at 1 since the base case of 0 is already set):

for t in range(1, target + 1):
    for coin in coins:
        if coin <= t:
            dp[t] = min(dp[t], 1 + dp[t - coin])

Once this is done, the answer to the problem will be stored in dp[target].

Implementation - Bottom-Up**

def min_coin_combination_bottom_up(coins: List[int], target: int) -> int:
    # The DP array will store the minimum number of coins needed for each amount. Set
    # each element to a large number initially.
    dp = [float('inf')] * (target + 1)
    # Base case: if the target is 0, then 0 coins are needed.
    dp[0] = 0
    # Update the DP array for all target amounts greater than 0.
    for t in range(1, target + 1):
        for coin in coins:
            if coin <= t:
                dp[t] = min(dp[t], 1 + dp[t - coin])
    return dp[target] if dp[target] != float('inf') else -1

#include <vector>
using namespace std;

int minCoinCombinationBottomUp(vector<int>& coins, int target) {
    const int INF = 1000000000;
    // dp[t] = fewest coins to make amount t; start everything at "infinity".
    vector<int> dp(target + 1, INF);
    dp[0] = 0;                          // base case: 0 coins make 0
    for (int t = 1; t <= target; t++) {
        for (int i = 0; i < (int)coins.size(); i++) {
            int coin = coins[i];
            if (coin <= t && dp[t - coin] != INF && dp[t - coin] + 1 < dp[t]) {
                dp[t] = dp[t - coin] + 1;
            }
        }
    }
    return dp[target] == INF ? -1 : dp[target];
}

// These methods live inside a class, e.g. class Solution { ... }
int minCoinCombinationBottomUp(int[] coins, int target) {
    final int INF = 1000000000;
    // dp[t] = fewest coins to make amount t; start everything at "infinity".
    int[] dp = new int[target + 1];
    Arrays.fill(dp, INF);
    dp[0] = 0;                          // base case: 0 coins make 0
    for (int t = 1; t <= target; t++) {
        for (int i = 0; i < coins.length; i++) {
            int coin = coins[i];
            if (coin <= t && dp[t - coin] != INF && dp[t - coin] + 1 < dp[t]) {
                dp[t] = dp[t - coin] + 1;
            }
        }
    }
    return dp[target] == INF ? -1 : dp[target];
}

Complexity Analysis

Time complexity: The time complexity of min_coin_combination_bottom_up is $O(targetn)$ because we loop through all $n$ coins for each value between 1 and $target$.

Space complexity: The space complexity is $O(target)$ due to the space occupied by the DP array, which is of size $target+1$.

Dry Runs

Two step-by-step walkthroughs of the algorithm below: a valid case (the expected happy path) and an invalid / edge case that exercises the tricky parts. Each step shows the program state as the code runs—the same steps apply to Python, C++ and Java.

The same steps in each language

Interview Tip

Tip: When a problem asks for the minimum or maximum of something, it might be a DP problem.
If you spot keywords like "minimum", "maximum", "longest", or "shortest", in the problem description, consider whether a DP approach might be appropriate, as many DP problems involve optimizing a certain value, such as finding the minimum cost, or longest sequence.