Problem: Coin Change

Problem Statement

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

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

Approach: Bottom-Up Tabulation

This is a variation of the Unbounded Knapsack problem.

State: dp[i] is the minimum coins needed for amount i.
Base Case: dp[0] = 0 (0 coins needed for amount 0).
Initialization: Fill dp with amount + 1 (a value larger than any possible answer).
Transition: For each amount i from 1 to amount:
- For each coin c:
  - If i - c >= 0, then dp[i] = min(dp[i], 1 + dp[i - c]).

Java Implementation

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;
    
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (i >= coin) {
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }
        }
    }
    
    return dp[amount] > amount ? -1 : dp[amount];
}

Complexity Analysis

Time Complexity: $O(A \times C)$ where $A$ is amount and $C$ is number of coins.
Space Complexity: $O(A)$.

Interview Tips