Crack the Backend

Problem Statement

Given an integer array coins (different denominations) and an integer amount, return the fewest number of coins needed to make that amount. If that amount cannot be made by any combination of the coins, return -1. You may use each coin unlimited times.

Each coin denomination can be used as many times as you want.
amount is non-negative; coins are positive integers.
If amount is 0, return 0 (no coins needed).

Key Observations

Let dp[a] = minimum number of coins needed to make amount a. For each a from 1 to amount, we can try using one coin of denomination c (if c <= a), leaving subproblem a - c: so dp[a] = 1 + min(dp[a-c]) over all coins c with c <= a.
Base: dp[0] = 0. Initialize other dp[a] with a value larger than any possible answer (e.g. amount + 1); if after the loop dp[amount] is still that sentinel, return -1.
Order of iteration (a from 1 to amount) ensures that when we compute dp[a], all dp[a-c] are already computed.

Approach

High-level: dp[a] = fewest coins to make amount a. For each a, try each coin c: if c <= a, dp[a] = min(dp[a], 1 + dp[a-c]). Base dp[0] = 0.

Steps:

dp[0] = 0; fill dp[1..amount] with amount + 1 (or Integer.MAX_VALUE - 1 to avoid overflow).
For a from 1 to amount: for each c in coins, if c <= a then dp[a] = min(dp[a], 1 + dp[a-c]).
Return dp[amount] > amount ? -1 : dp[amount].

Implementation

Java

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;

    for (int a = 1; a <= amount; a++) {
        for (int c : coins) {
            if (c <= a) {
                dp[a] = Math.min(dp[a], 1 + dp[a - c]);
            }
        }
    }

    return dp[amount] > amount ? -1 : dp[amount];
}

Test Cases

Example 1

Input

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

Expected

3

Explanation

11 = 5+5+1.

Complexity Analysis

Time: O(amount * len(coins)).
Space: O(amount).

Follow-ups

Return the actual combination of coins; count total number of ways to make amount.