def change(self, amount, coins):
"""
:type amount: int
:type coins: List[int]
:rtype: int
"""
dp = [0] * (amount + 1)
dp[0] = 1
for i in coins:
for j in range(1, amount + 1):
if j >= i:
dp[j] += dp[j  i]
return dp[amount]
python O(n) space dp solution


@yzj1212 My TLE 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(amount, coin1, 1): for n in range(1, i//coin+1): dp[i] += dp[i  n*coin] return dp[1]
After inspired by your codes, 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]





@LiWei Because coins' order does not matter. For the first example, in your case, dp[3] will be 3, which are '2+1', '1+2', and '1+1+1'. It should be 2, which are '1+2' and '1+1+1'.
