Python, 11-line, 280ms, DFS with early termination, 99% up


  • 8
    Z

    First sort the coins, we will deal with big coin first

    When there is no hope to reduce total count, stop the dfs

    def coinChange(self, coins, amount):
        coins.sort(reverse = True)
        lenc, self.res = len(coins), 2**31-1
        
        def dfs(pt, rem, count):
            if not rem:
                self.res = min(self.res, count)
            for i in range(pt, lenc):
                if coins[i] <= rem < coins[i] * (self.res-count): # if hope still exists
                    dfs(i, rem-coins[i], count+1)
    
        for i in range(lenc):
            dfs(i, amount, 0)
        return self.res if self.res < 2**31-1 else -1

  • 1
    Z

    I always have problem figuring out complexity for this kind of DFS, can anyone advise?


  • 0
    J

    Clever optimization here "coins[i] * (self.res-count)". I had the same dfs TLE. I added your optimization and it brought down the time from 340 to 40ms with my tests. I think the worst case is O(amount) if you have just ['1'] in coins.


  • 0
    D
    This post is deleted!

  • 0
    D

    It is a brilliant Solution!
    While I am trying to understand it, some improvement ideas pop up.
    Change 2 ** 31-1 to a smaller number
    amount//coins[-1]+1
    You are using 2**31-1 as the impossible answer. The maximum possible answer is that when you only use the smallest coin to get the amount which is amount//coins[-1], adding 1 on that gives us the boundary of all possible answer.

    Another possible improvement is to have a pre-check in the outer for loop, if the shortest path (amount//coins[i]+1)is already longer than self.res, then we can break the for loop.
    When the length of coin list is long, this improvement can contribute more.

    I made a test with my PC, result shows 16% speed gain with 5000 times run each solution.

    from timeit import timeit
    class Solution(object):   
        def coinChange(self, coins, amount):
            coins.sort(reverse = True)
            lenc, self.res = len(coins), 2**31-1
    
            def dfs(pt, rem, count):
                if not rem:
                    self.res = min(self.res, count) ## Find an solution, compare the count with global count. Maybe refrese the global count.
                for i in range(pt, lenc):
                    if coins[i] <= rem < coins[i] * (self.res-count): # if hope still exists
                        dfs(i, rem-coins[i], count+1)
    
            for i in range(lenc):
                dfs(i, amount, 0)
            return self.res if self.res < 2**31-1 else -1
        def coinChange2(self, coins, amount):
            coins.sort(reverse = True)
            lenc, self.res = len(coins), amount//coins[-1]+1
    
            def dfs(pt, rem, count):
                if not rem:
                    self.res = min(self.res, count) ## Find an solution, compare the count with global count. Maybe refrese the global count.
                for i in range(pt, lenc):
                    if coins[i] <= rem < coins[i] * (self.res-count): # if hope still exists
                        dfs(i, rem-coins[i], count+1)
            for i in range(lenc):
                if self.res < (amount//coins[i]+1):
                    break
                else:
                    dfs(i, amount, 0)
            return self.res if self.res < amount//coins[-1]+1 else -1
    
    
    print timeit('Solution().coinChange([186,419,83,408,32,31,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,13], 6249)', 'from __main__ import Solution', number = 5000)
    print timeit('Solution().coinChange2([186,419,83,408,32,31,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,13], 6249)', 'from __main__ import Solution', number = 5000)
    

    5.72996206357
    4.76601419506
    


  • 0
    L
    This post is deleted!

  • 0
    A

    @zhuyinghua1203 it will be be helpful to have more descriptive variable names. your solution is excellent, but it is very difficult to understand because of cryptic varibale names


  • 0
    Y

    @zhuyinghua1203 This is the best solution I have seen, better than the DP ones. If my understanding is correct then it is efficient because of optimally exploring the tree. In particular it explores branches by using as many of the largest coins as possible before moving on to smaller denominations. It also stops exploring when the branch could not give a better result than already found.

    Because of the optimal ordering it does not store the results of subproblems in a lookup table like DP. I wonder if storing any partial results could improve it further?

    Also there is no need to put the call to dfs(i, amount, 0) inside a for loop and try all coins. If you change it to dfs(0, amount, 0) it will start with the largest coin and explore all others.


Log in to reply
 

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