Problem Statement in English

You’re given an integer n. You need to find the least number of perfect square numbers that sum up to n.

Approach

This is an LIS style problem. The idea is that for each “subproblem”, where each subproblem is the number of perfect squares that sum up to it, we can use subproblems that are smaller than it to solve it.

So, in order to, say, x, we can use the perfect squares that are less than x to solve for it.

Solution in Python

  • Memoization (Time Limit Exceeded)

class Solution:
def numSquares(self, n: int) -> int:

    @cache
    def dp(n: int) -> int:
        if n == 0:
            return 0
        elif n == 1:
            return 1
        if n < 0:
            return float("inf") # type: ignore

        best = float("inf")

        for i in range(1, n):
            best = min(1 + dp(n - i**2), best)

        return best # type: ignore

    return dp(n)  # type:ignore
  • Tabulation
class Solution:
    def numSquares(self, n: int) -> int:
        cache = [float("inf")] * (n + 1)
        cache[0] = 0

        for subproblem in range(1, n + 1):
            for root in range(1, subproblem + 1):
                square = root**2
                if square <= subproblem:
                    cache[subproblem] = min(
                        cache[subproblem], 1 + cache[subproblem - square]
                    )
                else:
                    break

        return cache[-1]

Complexity

  • Time: $O(n^2)$
    Since we are iterating through all the numbers from 1 to n and for each number, we are iterating through all the perfect squares less than it.

  • Space: $O(n)$
    Where n is the input number.

And we are done.