# Some problem with python test cases?

• Code below gives TLE for different test cases on different submissions. When I copy and paste the same test case in custom input it runs in below 100ms for every test case every time. Also, while copying I noticed that these cases don't have proper formatting. Maybe that is the actual problem? Can someone please confirm

``````    if not amount:
return 0

import sys
dp = [sys.maxint]*(amount+1)

dp[0] = 0

coins = sorted(coins)

for i in xrange(1,amount+1):
for coin in coins:
if coin > i:
break
else:
if dp[i-coin] != sys.maxint:
dp[i] = min(dp[i], dp[i-coin] + 1)

return dp[-1] if dp[-1] != sys.maxint else -1``````

• No, the formatting isn't the problem, your solution is just too slow.

• Could you please suggest some improvements. Below is my accepted code but I don't understand why this little improvement should matter.
`if not amount:
return 0

``````    dp = [amount+1]*(amount+1)

dp[0] = 0

coins = sorted(coins)

for i in xrange(1,amount+1):
for coin in coins:
if coin > i:
break
else:
#if dp[i-coin] != sys.maxint:
dp[i] = min(dp[i], dp[i-coin] + 1)

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

Also, if you post your own python version it would be highly appreciated. I find something new in them always.

• I have tried this too without significant improvement(still beyond 1000ms):

``````for coin in coins:
for i in xrange(coin,amount+1):
dp[i] = min(dp[i], dp[i-coin]+1)

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

• Ok, here are mine. I got under 1000ms, but not by much.

• I had experimented with your code as well, and removing the extra test `if dp[i-coin] != sys.maxint` seemed to help the most. I guess it doesn't help very often/much, and it hurts too much to always run that extra test.

It's a bit like that `if not amount: return 0` thing that you and many others do. It's not needed, the rest of your solution would perfectly handle that case as well. And speedwise it only helps a tiny bit and only in rare cases that are fast anyway, and it slows down every other case a bit (so overall I'd say it hurts more than it helps, if it makes any difference at all). I only ever do something like that when I really need it, i.e., when the rest doesn't work otherwise. (Though not because of speed but because I don't like unnecessary code.)

• Thanks a lot for the suggestion. But I am still not satisfied with the speed. C++ gives much better result. I understand that python is slower but this slow?

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