Python with memoization gives TLE!

  • 0

    The below, top down memoized implementation which is giving TLE. Any thoughts why?

    EDIT: similar problem reported here -

    from functools import wraps
    def memo(func):
        cache = {}
        def wrap(*args):
            if args not in cache:
                cache[args] = func(*args)
            return cache[args]
        return wrap
    class Solution(object):
        def coinChange(self, coins, amount):
            :type coins: List[int]
            :type amount: int
            :rtype: int
            if len(coins) == 0:
                return -1
            self.coins = coins
            return self.change(amount)
        def change(self, amount):
            if amount == 0:
                return 0
            if amount < 0:
                return -1
            minCoins = float('inf')
            for coin in self.coins:
                res = self.change(amount - coin)
                if res > -1:
                    minCoins = min(minCoins, 1 + res)
            return minCoins if minCoins != float('inf') else -1

  • 0

    @ohmygeek It has happened to me on multiple occasions. Just as I add a simple line to the start and the end of my recursive program. TLE pops up.

Log in to reply

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