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]
