Documenting LeetCode solving.

Q119

518. Coin Change II

Medium. 2D DP

Spent a lot of time drawing the grid.

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [[0] * (amount + 1) for _ in range(len(coins) + 1)]
        for i in range(len(coins) + 1):
            dp[i][0] = 1

        for i in range(1, len(coins) + 1):
            for a in range(1, amount + 1):
                dp[i][a] = dp[i - 1][a]
                if a - coins[i - 1] >= 0:
                    dp[i][a] += dp[i][a - coins[i - 1]]

        return dp[len(coins)][amount]