Help! Time limit exceeded in python top-down memorization

  • 0
    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
                    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.