LeetCode #322: Coin Change

LeetCode Solutions

https://leetcode.com/problems/coin-change/

This problem can be solved using dynamic programming. We will use an array dp of length amount+1 to store the minimum number of coins needed to make up each amount from 0 to amount.

First, we initialize dp[0] to be 0, because it takes 0 coins to make up an amount of 0.

Next, we iterate through the amounts from 1 to amount and for each amount, we iterate through the coins. For each coin that is less than or equal to the current amount, we calculate the minimum number of coins needed to make up the current amount using the formula 1 + dp[current amount - coin]. We update the dp array with the minimum of the current value of dp and the newly calculated value.

Finally, we return dp[amount] if it is less than amount+1 (which is the initial value of dp[amount]). If dp[amount] is equal to amount+1, it means we were unable to make up the amount with the given coins and we return -1.

  1. Initialize an array dp of length amount+1 with each element initialized to amount+1.
  2. Set dp[0] = 0.
  3. Iterate through the amounts from 1 to amount.
  4. For each amount, iterate through the coins.
  5. For each coin that is less than or equal to the current amount, calculate the minimum number of coins needed to make up the current amount using the formula 1 + dp[current amount - coin].
  6. Update dp[current amount] with the minimum of the current value of dp and the newly calculated value.
  7. Return dp[amount] if it is less than amount+1, otherwise return -1.

Here is the solution in python3:

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [amount+1] * (amount+1)
        dp[0] = 0

        for ind in range(1, amount+1):
            for coin in coins:
                if ind - coin >= 0:
                    dp[ind] = min(dp[ind], 1 + dp[ind-coin])
        
        return dp[amount] if dp[amount] != amount + 1 else -1

Time and Space Complexity

The time complexity of this solution is O(amount * n), where n is the length of the coins array. This is because we are iterating through each amount from 1 to amount and for each amount, we are iterating through each coin.

The space complexity of this solution is O(amount+1) because we are using an array of length amount+1 to store the minimum number of coins needed for each amount.