Algorithm Day86 - Coin Change

Posted on In , Views:

🧩 Problem Description

You are given an integer array coins representing different denominations of coins 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 cannot be made up by any combination of the coins, return -1.

💬 Examples

Example 1

1
2
3
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2

1
2
Input: coins = [2], amount = 3
Output: -1

Example 3

1
2
Input: coins = [1], amount = 0
Output: 0

💡 Intuition

This is a classic DP problem similar to the unbounded knapsack problem.
We want the minimum number of coins to reach a target amount.

  • Define dp[i] = minimum coins needed for amount i.
  • Transition:
1
dp[i] = min(dp[i], dp[i - coin] + 1) for each coin <= i
  • Base: dp[0] = 0.

If no solution exists, dp[amount] remains infinity (-1).

🔢 Java Code (DP Bottom-Up)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;

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

⏱ Complexity Analysis

  • Time: O(amount * n), where n = number of coins.
  • Space: O(amount) for the DP array.

✍️ Summary

  • Classic coin change problem → DP solution.
  • Transition: dp[i] = min(dp[i - coin] + 1).
  • If no solution → return -1.

Related problems

  • lc-518 — Coin Change II (count ways instead of minimum).
  • lc-279 — Perfect Squares.