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 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
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:
dp = [amount+1]*(amount+1) dp = 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.)
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.