Coin Change 2

Intuition

Solution

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        ways = [0] * (amount + 1)
        ways[0] = 1
        for c in coins:
            for s in range(1, amount + 1):
                if s < c:
                    continue
                ways[s] += ways[s - c]
        return ways[-1]