class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        # 凑成amount需要的组合数
        # 当amount=0时，有金币无总额, dp[0]=1
        dp = [1] + [0] * amount
        for coin in coins:
            for i in range(amount+1):
                if i-coin>=0:
                    dp[i] += dp[i]
        return dp[amount]

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        # 凑成amount需要的组合数
        # 当amount=0时，有金币无总额, dp[0]=1
        dp = [1] + [0] * amount
        for coin in coins:
            for i in range(amount+1):
                if i-coin>=0:
                    dp[i] += dp[i]
        return dp[amount]

# 凑成amount需要的组合数 # 当amount=0时，有金币无总额, dp[0]=1