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 and Explanation

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

1. Initialization: We initialize dp with a size of amount + 1. dp[0] is 0 (no coins needed to make amount 0). The rest of the elements are initialized to amount + 1 (a value larger than any possible valid solution). This represents an impossible state initially.

2. Iteration: We iterate through each amount from 1 to amount. For each amount i, we iterate through each coin denomination c in coins.

3. DP Transition: If the coin c is less than or equal to the current amount i, it means we can use this coin. We update dp[i] with the minimum between its current value and dp[i - c] + 1. dp[i - c] represents the minimum coins needed for the remaining amount after using coin c, and we add 1 to account for using coin c.

4. Result: After iterating through all amounts, 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].

Code (C++)

#include <vector>
#include <limits> //for numeric_limits

class Solution {
public:
    int coinChange(std::vector<int>& coins, int amount) {
        std::vector<int> dp(amount + 1, amount + 1); // Initialize dp array
        dp[0] = 0; // Base case: 0 coins needed to make amount 0

        for (int i = 1; i <= amount; ++i) {
            for (int coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = std::min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] > amount ? -1 : dp[amount]; //Return -1 if impossible
    }
};

Complexity Analysis

• Time Complexity: O(amount * n), where n is the number of coin denominations. This is because we have nested loops iterating through amounts and coins.

• Space Complexity: O(amount), due to the dp array of size amount + 1.

This detailed explanation and code provide a clear understanding of how to solve the Coin Change problem using dynamic programming in C++. Remember to include <vector> and <limits> for the code to compile correctly.