Help! Time limit exceeded in python top-down memorization


  • 0
    S
    class Solution(object):
        def coinChange(self, coins, amount):       
            def helper(coins, remains, memo):
                if remains == 0: return 0
                if remains < 0: return -1
                
                res = memo.get(remains)
                if res: return res
                
                minRes = remains + 1
                for i in range(len(coins)):
                    res = helper(coins, remains-coins[i], memo)
                    if res != -1:
                        minRes = min(minRes, res+1)
                
                if minRes != remains + 1:     
                    memo[remains] = minRes
                    return minRes
                else:
                    return -1
            return helper(coins, amount, dict())
    

    According to the solution, the complexity of the code should be O(S*n), where S is the original amount and n is coin types, because there are 1...S entries in the memorization, and each entry is created by going through the coin array once.


Log in to reply
 

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