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

1. Initialization: Create a DP (Dynamic Programming) array dp of size amount + 1. Initialize all elements of dp to amount + 1 (a value larger than any possible solution). dp[i] will store the minimum number of coins needed to make up amount i. Set dp[0] = 0 because it takes 0 coins to make amount 0.

2. Iteration: Iterate through each coin c in coins. For each coin, iterate through the dp array from c to amount. For each index i, update dp[i] with the minimum between its current value and dp[i - c] + 1. dp[i - c] + 1 represents the number of coins needed if we use one coin of denomination c.

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, so return -1. Otherwise, return dp[amount].

Explanation

This solution utilizes dynamic programming to efficiently find the minimum number of coins. The DP array stores the minimum number of coins needed for each amount from 0 to the target amount. The algorithm iteratively builds up the solution by considering each coin denomination and its contribution to different amounts. By taking the minimum between the current value and a new possible solution using a given coin, we ensure that we always keep track of the optimal solution.

Code

function coinChange(coins: number[], amount: number): number {
    const dp: number[] = new Array(amount + 1).fill(amount + 1);
    dp[0] = 0;

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

    return dp[amount] === amount + 1 ? -1 : dp[amount];
};

Complexity

• Time Complexity: O(amount * n), where n is the number of coins. This is because of the nested loops iterating through coins and amounts.
• Space Complexity: O(amount), due to the size of the DP array.