Coin Change (Minimum Coins)

Intuition

dp[i] = minimum coins to make sum i. For each coin c and each amount w >= c: dp[w] = min(dp[w], dp[w-c]+1). Initialize dp[1..sum] = INF.

Algorithm

1dp[0]=0, dp[1..sum]=INF.
2For each coin c: for w from c to sum: if dp[w-c] != INF: dp[w]=min(dp[w], dp[w-c]+1).
3Return dp[sum] if not INF, else âˆ’1.

Example Walkthrough

Input: coins=[1,5,6,9], sum=11

1.dp[5]=1, dp[6]=1, dp[9]=1. dp[10]=2(5+5 or 4+6...). dp[11]=2 (5+6).

Output: 2

Common Pitfalls

•Return âˆ’1 if dp[sum] remains INF â€” the sum is unreachable.

Coin Change (Minimum Coins).java

Java

// Approach: DP. dp[i] = minimum coins needed to make amount i.
// For each coin, dp[j] = min(dp[j], dp[j-coin]+1) for j from coin to amount.
// Time: O(n * amount) Space: O(amount)
class Solution {

    public int minCoins(int coins[], int sum) {
        // Tabulation
        int n = coins.length;
        int[][] dp = new int[n][sum + 1];

        for (int i = 0; i <= sum; i++) {
            if (i % coins[0] == 0)
                dp[0][i] = i / coins[0];
            else
                dp[0][i] = (int) (1e9);
        }

        for (int ind = 1; ind < n; ind++) {
            for (int target = 0; target <= sum; target++) {
                int notTake = dp[ind - 1][target];
                int take = Integer.MAX_VALUE;

                if (coins[ind] <= target)
                    take = 1 + dp[ind][target - coins[ind]];

                dp[ind][target] = Math.min(take, notTake);
            }
        }
        
        return dp[n - 1][sum] >= (int) (1e9) ? -1 : dp[n - 1][sum];
    }
}

Was this solution helpful?