LeetCode 322: Coin Change — Step-by-Step Visual Trace

#leetcode #algorithms #python #dynamicprogramming

Medium — Dynamic Programming | Array | Greedy

The Problem

Given an array of coin denominations and a target amount, find the minimum number of coins needed to make up that amount, or return -1 if it's impossible.

Approach

Uses dynamic programming with a bottom-up approach. We build a DP array where dp[i] represents the minimum coins needed for amount i, iterating through each coin type and updating the minimum coins required for each possible amount.

Time: O(amount × coins) · Space: O(amount)

Code

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # Initialize the DP array with a maximum value to represent impossible cases.
        dp = [float("inf")] * (amount + 1)

        # Base case: It takes 0 coins to make up the amount of 0.
        dp[0] = 0

        # Iterate through the DP array and update the minimum number of coins needed.
        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] = min(dp[i], dp[i - coin] + 1)

        # If dp[amount] is still float('inf'), it means it's impossible to make up the amount.
        # Otherwise, dp[amount] contains the minimum number of coins needed.
        return dp[amount] if dp[amount] != float("inf") else -1