6-7 lines, 2 ways


  • 10

    I'm surprised that out of all solutions so far, only yular used the coins for the outer loop. Everybody else used the amount for the outer loop. Making coins the outer loop saves the extra "if" and quite some time. Here's a comparison of both ways.

    Solution 1, coins outer loop, average 92ms

    int coinChange(vector<int>& coins, int amount) {
        vector<int> need(amount+1, amount+1);
        need[0] = 0;
        for (int c : coins)
            for (int a=c; a<=amount; a++)
                need[a] = min(need[a], need[a-c] + 1);
        return need.back() > amount ? -1 : need.back();
    }
    

    Solution 2, amount outer loop, average 180ms

    int coinChange(vector<int>& coins, int amount) {
        vector<int> need(amount+1, amount+1);
        need[0] = 0;
        for (int a=1; a<=amount; a++)
            for (int c : coins)
                if (c <= a)
                    need[a] = min(need[a], need[a-c] + 1);
        return need.back() > amount ? -1 : need.back();
    }

  • 0
    B

    @StefanPochmann , can you explain why execution time is different? Tested the same thing and got similar results.


  • 0
    S

    Could you please translate the codes into python? Really appreciates. Thanks.


  • 3
    P

    @sbdust

    def coinChange(self, coins, amount):
        # need = [amount + 1] * (amount + 1)
        # need[0] = 0
    
        need = [0] + [amount + 1] * amount
       
        for c in coins:
            for a in xrange(c, amount + 1):
                need[a] = min(need[a], need[a - c] + 1)
        
        return -1 if need[-1] > amount else need[-1]

  • 0

    @pankesh Easy to combine the first two lines in Python...


  • 0
    B

  • 0
    P

    @broccoli I edited the code. Please see the comments now. Sorry for confusion.


  • 0
    S

    Thanks to you guys.


  • 0

    @StefanPochmann
    I found there is little difference in Python for these two solution.
    The first 1600ms+ and the second 1500ms+


Log in to reply
 

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