Medium — Dynamic Programming | Array | Coin Change

The Problem

Given an array of coin denominations and a target amount, find the number of different combinations of coins that make up that amount.

Approach

Uses dynamic programming with a 1D array where dp[i] represents the number of ways to make amount i. For each coin, we iterate through all amounts and update the number of combinations by adding the ways to make (current_amount - coin_value).

Time: O(n * m) · Space: O(n)

Code

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        # Initialize a 1D array dp to store the number of combinations for each amount from 0 to amount.
        dp = [0] * (amount + 1)

        # There is one way to make amount 0 (by not using any coins).
        dp[0] = 1

        # Iterate through each coin denomination.
        for coin in coins:
            # Update the dp array for each amount from coin to amount.
            for i in range(coin, amount + 1):
                dp[i] += dp[i - coin]

        # The dp[amount] contains the number of combinations to make the target amount.
        return dp[amount]

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment