Problem: Coin Change (Minimum Coins)

You are given a list of coins with different denominations and a target amount. The goal is to determine the fewest number of coins needed to make up that amount. If it’s impossible to make up that amount, return -1.

Dynamic Programming Approach Explanation:

This is a classic problem that can be solved using Dynamic Programming (DP). We will use a bottom-up approach where we build the solution incrementally, starting from the smallest subproblems (amount 0) and gradually increasing to the target amount.

Concept:

1. State Representation:
   Let dp[i] represent the fewest number of coins required to make amount i.

2. Initialization:

   • Set dp[0] = 0, because zero amount requires zero coins.
   • For other amounts i > 0, initialize dp[i] = infinity (or a large value) because initially, we assume it’s impossible to form that amount.

3. State Transition:
   For each coin denomination, update the dp array. If we can make the amount i - coin, then we can make the amount i by adding one more coin. Therefore:

   dp[i]=min⁡(dp[i],dp[i−coin]+1)dp[i] = min(dp[i], dp[i – coin] + 1)

4. Final Answer:
   After processing all coins, dp[amount] will give the minimum number of coins required for the target amount. If dp[amount] is still infinity, it means the target amount cannot be formed with the given coins, and we return -1.

Example:

Input:
coins = [1, 2, 5], amount = 11

Step-by-step DP Table:

Answer: 3, because we need 3 coins: 5 + 5 + 1.

C Code:

#include <stdio.h>
#include <limits.h>

int coinChange(int* coins, int coinsSize, int amount) {
    int dp[amount + 1];
    
    // Initialize the dp array with a large value
    for (int i = 0; i <= amount; i++) {
        dp[i] = INT_MAX;
    }
    dp[0] = 0;  // No coins needed to make amount 0
    
    // Bottom-up DP
    for (int i = 1; i <= amount; i++) {
        for (int j = 0; j < coinsSize; j++) {
            if (i >= coins[j] && dp[i - coins[j]] != INT_MAX) {
                dp[i] = dp[i] < dp[i - coins[j]] + 1 ? dp[i] : dp[i - coins[j]] + 1;
            }
        }
    }
    
    // If dp[amount] is still INT_MAX, it means we cannot form the amount
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

int main() {
    int coins[] = {1, 2, 5};
    int coinsSize = 3;
    int amount = 11;
    
    int result = coinChange(coins, coinsSize, amount);
    printf("Minimum number of coins: %dn", result);
    return 0;
}

Python Code:

def coinChange(coins, amount):
    # Initialize dp array with infinity, except dp[0] which is 0
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    # Bottom-up DP
    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    # If dp[amount] is still infinity, return -1, otherwise return dp[amount]
    return dp[amount] if dp[amount] != float('inf') else -1

# Example Usage:
coins = [1, 2, 5]
amount = 11
result = coinChange(coins, amount)
print(f"Minimum number of coins: {result}")

Explanation of Code:

1. Initialization:

   • In both C and Python, the dp array is initialized to represent the fewest coins needed for every amount from 0 to amount. Initially, all amounts are set to a large value (INT_MAX in C and float('inf') in Python) except dp[0], which is set to 0 (because no coins are needed to make amount 0).

2. Filling the DP Table:

   • For each amount from 1 to amount, iterate through each coin. If we can use that coin (i.e., i >= coin), then update the dp[i] value by considering using that coin: dp[i]=min⁡(dp[i],dp[i−coin]+1)dp[i] = min(dp[i], dp[i – coin] + 1)
   • This ensures we get the minimum number of coins for each amount.

3. Final Check:

   • After filling the DP table, if dp[amount] is still infinity (INT_MAX or float('inf')), it means it’s not possible to make that amount with the given coins, so return -1. Otherwise, return dp[amount], which is the minimum number of coins needed.

Time and Space Complexity:

• Time Complexity:

  • The time complexity is O(amount * coins), where amount is the target amount and coins is the number of coin denominations. For each amount, we check every coin denomination.

• Space Complexity:

  • The space complexity is O(amount) because we only need a dp array of size amount + 1.

Example Output:

1. Input:
   coins = [1, 2, 5], amount = 11

   Output:
   3 (because 11 = 5 + 5 + 1)

2. Input:
   coins = [2], amount = 3

   Output:
   -1 (because it’s impossible to make amount 3 with only coin 2)

3. Input:
   coins = [1], amount = 0

   Output:
   0 (no coins needed to make amount 0)

This dynamic programming approach is efficient and works well within the given problem constraints.