Why my Python Solution has MLE?


  • 0
    V

    Hello guys, I really confused that my Python recursive solution failed Memory Limit Exceeded.

    Actually, I almost use the same way from the recursive method in this post (He just Java, I use Python)
    https://discuss.leetcode.com/topic/32489/java-both-iterative-and-recursive-solutions-with-explanations

    Here is my code:

    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        if amount==0: return 0
        self.MAX=float('inf')
        self.dp=[0]*amount
        return self.helper(coins,amount)
        
    def helper(self,coins,amount):
        if amount<0: return -1
        if amount==0: return 0
        if self.dp[amount-1]!=0: 
            return self.dp[amount-1]
        min=self.MAX
        for coin in coins:
            val=self.helper(coins,amount-coin)
            if val>=0 and val+1<min:
                min=val+1
        self.dp[amount-1]=min if min!=self.MAX else -1
        return self.dp[amount-1]

Log in to reply
 

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