Clean dp python code


  • 28

    Assume dp[i] is the fewest number of coins making up amount i, then for every coin in coins, dp[i] = min(dp[i - coin] + 1).

    The time complexity is O(amount * coins.length) and the space complexity is O(amount)

    class Solution(object):
        def coinChange(self, coins, amount):
            MAX = float('inf')
            dp = [0] + [MAX] * amount
    
            for i in xrange(1, amount + 1):
                dp[i] = min([dp[i - c] if i - c >= 0 else MAX for c in coins]) + 1
    
            return [dp[amount], -1][dp[amount] == MAX]

  • 0
    V

    Hi shiyanhui, thanks for sharing your dp solution! I tried to follow along but didn't quite understand what's going on in the for loop. Could you share how you formed this dp solution? Thanks!

    Also, what would the time complexity be for this algorithm? Is it O(n*m) where n = amount and m = number of coins?


  • 1
    M

    I think my dp solution is the same as yours, but why mine is TLE? thank you!

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

  • 1

    Hello, I updated the description of this solution. The time complexity is O(amount * coins.length).


  • 2

    First list comprehensions is faster than for, and there are more judgment statement in your solution.

    I chosen a test sample coinChange([19,28,176,112,30,260,491,128,70,137,253], 8539), below is performance comparison.

    This is mine

    ➜  LeetCode  python -m cProfile 322\ Coin\ Change.py
    21
             8543 function calls in 0.020 seconds
    
       Ordered by: standard name
    
       ncalls  tottime  percall  cumtime  percall filename:lineno(function)
            1    0.000    0.000    0.020    0.020 322 Coin Change.py:22(<module>)
            1    0.000    0.000    0.000    0.000 322 Coin Change.py:25(Solution)
            1    0.017    0.017    0.020    0.020 322 Coin Change.py:35(coinChange)
            1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
         8539    0.004    0.000    0.004    0.000 {min}
    

    And this is yours

    ➜  LeetCode  python -m cProfile 322\ Coin\ Change.py
    21
             92243 function calls in 0.043 seconds
    
       Ordered by: standard name
    
       ncalls  tottime  percall  cumtime  percall filename:lineno(function)
            1    0.000    0.000    0.043    0.043 322 Coin Change.py:22(<module>)
            1    0.000    0.000    0.000    0.000 322 Coin Change.py:25(Solution)
            1    0.000    0.000    0.000    0.000 322 Coin Change.py:45(Solution)
            1    0.030    0.030    0.043    0.043 322 Coin Change.py:46(coinChange)
            1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        92236    0.013    0.000    0.013    0.000 {min}
            2    0.000    0.000    0.000    0.000 {range}
    

    The time yours costs is almost 2 times as mine. There are more call of function min, and this comparison dp[i - coin] != -1 is useless because dp[i] could't be negative.


  • 0
    E

    Hi, thanks for sharing your solution. I been looking for texts or videos to learn DP but haven't been able to fully understand this topic yet. Do you have any material you can share?
    Thank in advance!


  • 0
    Y

    I still don't understand why amount is in the outer loop and coins in inner loop and the other way around would result in wrong answer.


Log in to reply
 

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