# Dp solution with python Time Limit Exceeded . Any suggest to pass

• This is my code :

``````def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
if amount <= 0:
return -1

dp = [amount + 1] * (amount + 1)
dp[0] = 0
for i in xrange(1,amount+1):
for j in xrange(len(coins)):
if coins[j] <= i:
dp[i] = min(dp[i],dp[i-coins[j]] + 1)
return -1 if dp[amount] == amount + 1 else dp[amount]
``````

Time Limit Exceeded with :
[333,364,408,118,63,270,69,111,218,371,305]
5615

Could someone give me some suggest to pass ?
thanks

• I suggest to sort the coins first into ascending order. Then, in your inner for loop, as soon as the if statement is not satisfied, break out of it.

• I have tried with your suggests, but it doesn't work.

• I can't imagine why. Take a look at my solution
https://leetcode.com/discuss/105862/python-solution

It's not much different. I got the idea from reading your solution.

• I get it from your solution . In python ,"for j in xrange(len(coins)):" is slower than "for j in coins:" . When I update this , it accepted. thx!

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