Menu

Subscribe

Perfect Squares

on dynamic programming, algorithms, unlisted, recursion

Problem

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Examples:

Input: n = 12  
Output: 3  
Explanation: 12 = 4 + 4 + 4.

Input: n = 13  
Output: 2  
Explanation: 13 = 4 + 9.

Input

  • n - integer

Approach

The brute force approach is to recursively use each perfect square number (\(1, 4, 9, 16...\)) and find a combination such that it gives us the least numbers to sum. The time complexity here is exponential.

The recursion is based off of the following recurrence relation:

\( leastSquares = min(f((total - perfSquares[j]), i+1), f(total, i)) \)

One optimization is to cache results, using a hash table, and recursively iterate from the smallest perfect square to the biggest perfect square. At each total, cache it into the hash map if it does not exist in the hash map; otherwise, read off of the cache to save some performance.

A better optimization than the former is to use dynamic programming -- that is, a bottom-up solution. In this optimization, instead of opting for recursion, we use a 2D array to pre-compute values, and use the recurrence relation formula above as the basis to populate the entire 2D array.

Solution

Note: We can improve this DP solution even further. Could you think of how?

    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        perf_sqs = []
        for i in range(1, int(math.sqrt(n)) + 1):
            perf_sqs.append(i ** 2)
        m = len(perf_sqs) - 1

        cache = [[0 for _ in range(n+1)] for _ in range(m+1))]

        for i in range(0, n+1):
            cache[0][i] = i

        for j in range(1, m+1):
            for i in range(0, n+1):
                if i >= perf_sqs[j]: 
                    cache[j][i] = min(cache[j][i - perf_sqs[j]] + 1, cache[j-1][i])
                else:
                    cache[j][i] = cache[j-1][i]

        return cache[m][n]

Solution #2

This variation reduces space complexity by only using a 1D array, and improves time complexity by only taking advantage of square roots.

    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        perf_sqs = []
        for i in range(1, int(math.sqrt(n)) + 1):
            perf_sqs.append(i ** 2)

        cache = [0 for _ in range(n+1)]

        for i in range(0, n+1):
            cache[i] = i

        for i in range(1, n+1):
            for j in range(0, int(math.sqrt(i))):
                cache[i] = min(cache[i - perf_sqs[j]] + 1, cache[i])

        return cache[n]