Python solution with detailed solution


  • 0
    G

    Solution

    Perfect Squares https://leetcode.com/problems/perfect-squares/

    Memoization based Solution

    • Draw a recursion tree with initial states being 1, 4, 9, 16...unit sqrt(N)
    from math import sqrt
    class Solution(object):
        def helper(self, n, cache):
            if n <= 1:
                return n
            elif n in cache:
                return cache[n]
            else:
                s = int(sqrt(n))
                cache[n] = float('inf')
                for j in range(s,0,-1):
                    cache[n] = min(cache[n], self.helper(n-j*j, cache) + 1)
                return cache[n]
        
        def numSquares(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n<= 1:
                return 1
            return self.helper(n, {})
    

    Breadth-First Solution

    • Can solve using BFS as well.

Log in to reply
 

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