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

**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

```python
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
```

## Watch It Run

> **[Open interactive visualization](https://tracelit.dev/app?trace=0322_coin-change)**

> **Try it yourself:** Open [TraceLit](https://tracelit.dev/app?trace=0322_coin-change) and step through every line.

---

*Built with [TraceLit](https://tracelit.dev) — the visual algorithm tracer for LeetCode practice.*