518. Coin Change 2

Approach 1: Dynamic Programming

class Solution(object):
    def change(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int
        """
        coins.sort()
        dp = [1] + [0] * (amount)
        for coin in coins:
            for i in range(-coin + amount + 1):
                dp[i+coin] += dp[i]
        return dp[amount]