Coin Change medium

Problem Statement

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

You may assume that you have an infinite number of each kind of coin.

Example 1:

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

Example 2:

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

Steps to Solve

This problem can be efficiently solved using dynamic programming. We'll create an array dp where dp[i] represents the minimum number of coins needed to make up the amount i.

1. Initialization: Create a dp array of size amount + 1 and initialize all elements to amount + 1 (a value larger than any possible valid solution). dp[0] is initialized to 0, as it takes 0 coins to make an amount of 0.

2. Iteration: Iterate through each coin denomination c in coins. For each coin, iterate through the dp array from c to amount. For each index i, we update dp[i] if using the current coin c results in a smaller number of coins: dp[i] = Math.min(dp[i], dp[i - c] + 1). This means we are checking if adding the current coin c to the minimum number of coins needed for i-c results in a better solution than the current minimum for i.

3. Result: After iterating through all coins, dp[amount] will contain the minimum number of coins needed to make up the amount. If dp[amount] is still amount + 1, it means it's impossible to make up the amount, so we return -1. Otherwise, we return dp[amount].

Explanation

The dynamic programming approach builds up the solution bottom-up. It leverages the fact that the minimum number of coins needed for a given amount is related to the minimum number of coins needed for smaller amounts. By iterating through coins and amounts, we explore all possible combinations efficiently. The Math.min operation ensures that we always keep track of the optimal (minimum) solution.

Code (Java)

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

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

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

Complexity

• Time Complexity: O(S*n), where n is the number of coins and S is the amount. We iterate through the coins array once for each amount.
• Space Complexity: O(S), where S is the amount. We use a dp array of size amount + 1.