def change(self, amount, coins):
dp = [1] + [0] * amount
for c in coins:
for i in range(1, amount + 1):
if i >= c:
dp[i] += dp[i  c]
return dp[1]
Classic problem, python clean DP O(MN)

@zhongyuan9817 My codes:
class Solution(object): def change(self, amount, coins): """ :type amount: int :type coins: List[int] :rtype: int """ dp = [ 1 if i == 0 else 0 for i in range(amount+1) ] for coin in coins: for i in range(coin, amount+1): dp[i] += dp[icoin] return dp[1]