# python O(n) space dp solution

• ``````    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]
``````

• Genius!
How did you come up with this?

• @WrenChan My girl friend inspired me

• Awesome! Neat and beautiful 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, coin-1, -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[i-coin]
return dp[-1]

``````

• @yzj1212 why this? dp[0] = 1, shouldn't it be dp[0]=0?

• @seetharami this would fix it:
dp[0]=1
if amount <= 0:
return 0

• @yzj1212 marry her :D Cheers!

• @07bit122 haha! Will do!

• My code is wrong, it is similar to your code. Could tell me why ??

``````        dp = [0]*(amount+1)
dp[0] = 1
for n in range(1, amount+1):
for i in coins:
if n >= i:
dp[n] += dp[n-i]
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'.

• @TianQ 哦~~想了半天没搞明白，你一说一下就明白了

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.