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


  • 0
    Z

    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


  • 0
    H

    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
    Z

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


  • 0
    H

    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.


  • 0
    Z

    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.