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

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

1. Initialization: Create a DP array dp 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 because it takes 0 coins to make an amount of 0.

2. Iteration: Iterate through each coin denomination coin in coins. For each coin, iterate through the DP array from coin to amount. For each index i, if dp[i - coin] + 1 is less than dp[i], it means we've found a better way to make up the amount i using the current coin. Update dp[i] accordingly.

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 the amount cannot be made up using the given coins, so we return -1. Otherwise, we return dp[amount].

Explanation

The dynamic programming approach builds up a solution from smaller subproblems. dp[i] represents the solution for a smaller amount i. By iterating through the coins and updating dp[i] based on previously computed values, we efficiently explore all possible combinations of coins to find the optimal solution. The initialization to amount + 1 ensures that any unreachable amount will remain at that value, helping us identify cases where the amount cannot be made.

Code

public class Solution {
    public int CoinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Array.Fill(dp, amount + 1);
        dp[0] = 0;

        foreach (int coin in 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(amount * n), where n is the number of coins. This is due to the nested loops iterating through the coins and the DP array.
• Space Complexity: O(amount), the space used by the DP array.