Coin Change Using Dynamic Programming

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Your task is to return the fewest number of coins needed to make up that amount. If the amount 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

Input:

• coins = [1,2,5]
• amount = 11

Output: 3

Explanation: 11 can be made with 5 + 5 + 1.

Solution Approach

To solve this problem efficiently, we use dynamic programming. The idea is to build up a solution incrementally by solving smaller subproblems first and using those solutions to solve larger subproblems. Here's a step-by-step breakdown of the approach:

1. Initialization: We create a dp array of size amount + 1, initialized to amount + 1 (a value greater than any possible number of coins). This array will store the minimum number of coins needed for each amount from 0 to amount. We set dp[0] = 0 because zero coins are needed to make the amount 0.
2. Dynamic Programming Transition: We iterate through each coin and then through each subamount from the coin value to the total amount. For each subamount, we update the dp array with the minimum number of coins needed:
3. Result Extraction: After processing all coins, if dp[amount] remains amount + 1, it means that the amount cannot be formed with the given coins, and we return -1. Otherwise, we return dp[amount].

Solution:

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount==0:
            return 0
        dp=[amount+1]*(amount+1)
        dp[0]=0
        for coin in coins:
            for i in range(coin,amount+1):
                dp[i]= min(dp[i],dp[i-coin]+1)
        if dp[amount]==amount+1:
            return -1
                    
        return dp[amount]        
                

Time Complexity

The time complexity of this solution is O(n * m), where n is the amount and m is the number of coins. This is because we have a nested loop: the outer loop runs for each coin and the inner loop runs for each subamount.

Space Complexity

The space complexity is O(n), where n is the amount. We use a single dp array of size amount + 1 to store our intermediate results.