LC-0518 Medium LeetCode

518. Coin Change II

Array Dynamic Programming

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 63% Topics: Array, Dynamic Programming

View full problem on LeetCode

Also on leetcode.ca (community mirror)

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min

Reference solution (spoiler · python)

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]

Solution from kamyu104/LeetCode-Solutions · MIT