Python with memoization gives TLE!


  • 0
    O

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

    EDIT: similar problem reported here - https://discuss.leetcode.com/topic/32489/java-both-iterative-and-recursive-solutions-with-explanations/6

    from functools import wraps
    
    def memo(func):
        cache = {}
        @wraps(func)
        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
            self.coins.sort(reverse=True)
            
            return self.change(amount)
        
        @memo
        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
    N

    @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.