# Clean dp python code

• Assume `dp[i]` is the fewest number of coins making up amount `i`, then for every `coin` in `coins`, dp[i] = min(dp[i - coin] + 1).

The time complexity is `O(amount * coins.length)` and the space complexity is `O(amount)`

``````class Solution(object):
def coinChange(self, coins, amount):
MAX = float('inf')
dp = [0] + [MAX] * amount

for i in xrange(1, amount + 1):
dp[i] = min([dp[i - c] if i - c >= 0 else MAX for c in coins]) + 1

return [dp[amount], -1][dp[amount] == MAX]``````

• Hi shiyanhui, thanks for sharing your dp solution! I tried to follow along but didn't quite understand what's going on in the for loop. Could you share how you formed this dp solution? Thanks!

Also, what would the time complexity be for this algorithm? Is it O(n*m) where n = amount and m = number of coins?

• I think my dp solution is the same as yours, but why mine is TLE? thank you!

``````class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""

dp = [0] + [amount + 1 for i in range(amount)]

for i in range(1, amount + 1):
for coin in coins:
if coin > i:
continue
elif dp[i - coin] != -1:
dp[i] = min(dp[i], dp[i - coin] + 1)

if dp[-1] == amount + 1:
return -1
else:
return dp[-1]``````

• Hello, I updated the description of this solution. The time complexity is `O(amount * coins.length)`.

• First `list comprehensions` is faster than `for`, and there are more judgment statement in your solution.

I chosen a test sample `coinChange([19,28,176,112,30,260,491,128,70,137,253], 8539)`, below is performance comparison.

This is mine

``````➜  LeetCode  python -m cProfile 322\ Coin\ Change.py
21
8543 function calls in 0.020 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
1    0.000    0.000    0.020    0.020 322 Coin Change.py:22(<module>)
1    0.000    0.000    0.000    0.000 322 Coin Change.py:25(Solution)
1    0.017    0.017    0.020    0.020 322 Coin Change.py:35(coinChange)
1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
8539    0.004    0.000    0.004    0.000 {min}
``````

And this is yours

``````➜  LeetCode  python -m cProfile 322\ Coin\ Change.py
21
92243 function calls in 0.043 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
1    0.000    0.000    0.043    0.043 322 Coin Change.py:22(<module>)
1    0.000    0.000    0.000    0.000 322 Coin Change.py:25(Solution)
1    0.000    0.000    0.000    0.000 322 Coin Change.py:45(Solution)
1    0.030    0.030    0.043    0.043 322 Coin Change.py:46(coinChange)
1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
92236    0.013    0.000    0.013    0.000 {min}
2    0.000    0.000    0.000    0.000 {range}
``````

The time yours costs is almost 2 times as mine. There are more call of function `min`, and this comparison `dp[i - coin] != -1` is useless because `dp[i]` could't be negative.

• Hi, thanks for sharing your solution. I been looking for texts or videos to learn DP but haven't been able to fully understand this topic yet. Do you have any material you can share?