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

  • 0

    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 :

    Could someone give me some suggest to pass ?

  • 0

    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.

  • 0

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

  • 0

    I can't imagine why. Take a look at my solution

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

  • 0

    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!

Log in to reply

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