Python O(amount) space, O(n*amount) time complexity


  • 0
    Z
    class Solution(object):
        def coinChange(self, coins, amount):
            """
            :type coins: List[int]
            :type amount: int
            :rtype: int
            """
            if amount == 0:
                return 0
            dp = [amount+1]*(1+amount)
            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[-1] == amount+1 else dp[-1]
    

    Used the similar method, got TLE first.

    OJ passed with 1728ms after using coin instead of coins[j]:

    class Solution(object):
        def coinChange(self, coins, amount):
            """
            :type coins: List[int]
            :type amount: int
            :rtype: int
            """
            if amount == 0:
                return 0
            dp = [amount+1]*(1+amount)
            dp[0] = 0
            for i in xrange(1,amount+1):
                for coin in coins:
                    if coin<=i:
                        dp[i] = min(dp[i],dp[i-coin]+1)
            return -1 if dp[-1] == amount+1 else dp[-1]

  • 0
    S

    I used similar method, 1820ms passed. So I guess the TLE bound should be around 2 seconds. not your fault


  • 0
    Z

    Thanks for your reply, so can you post your solution here?


  • 1

    here is my solution
    it gets 1800+ms.
    use "for coin in coins:" instead of "for j in xrange(len(coins)):"

    ps: my solution about this problem(c++/java/python):leetcode Coin Change

    class Solution(object):
        def coinChange(self, coins, amount):
            """
            :type coins: List[int]
            :type amount: int
            :rtype: int
            """
            if not amount: return 0
            INF = 0x7ffffffe
            dp = [INF] * (amount + 1)
            dp[0] = 0
            for i in xrange(amount + 1):
                for coin in coins:
                    if i + coin <= amount:
                        dp[i+coin] = min(dp[i+coin],dp[i] + 1)
            return dp[amount] if dp[amount] != INF else -1
    

  • 0
    B

    Thanks for sharing the trick . It worked for me :)


  • 0
    Z

    thanks, it passed the oj when using coin instead of coins[j]


Log in to reply
 

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