Teaching Kids Programming – Dynamic Programming Algorithms to Compute the Least Number of Perfect Squares

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given an integer n, return the least number of perfect square numbers that sum to n. A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

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

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

Constraints:
1 <= n <= 10^4

Greedy approach doesn’t work. For example, 23 is equal to 9 + 9 + 4 + 1 but if you go for greedy which to pick the largest square number less than N, then it will be equal to 16 + 4 + 1 + 1 + 1 which is not optimial.

Mathematically proven, we need at most four perfect square numbers to sum up to a positive integer.

Top-Down Dynamic Programming Algorihtm to Compute the Perfect Squares

For example, we can use F(N) to represent the least number of perfect squares to sum up to N, then we can memorize it via Dynamic Programming process:

where

The base case is

Using the @cache keyword or @lru_cache(None) or @lru_cache(maxsize=None) as the Memoization Technique together with Recursion which virtually make it Top-Down Dynamic Programming Algorithm:

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    @cache
    def numSquares(self, n: int) -> int:
        if n == 0:
            return 0
        i = 1
        ans = float("inf")
        while i * i <= n:
            ans = min(ans, self.numSquares(n - i * i) + 1)
            i += 1
        return ans

class Solution:
    @cache
    def numSquares(self, n: int) -> int:
        if n == 0:
            return 0
        i = 1
        ans = float("inf")
        while i * i <= n:
            ans = min(ans, self.numSquares(n - i * i) + 1)
            i += 1
        return ans

Time complexity is . Space complexity is O(N). This is Top-Down process as we are computing the F(N) and then recursively computing smaller F(i) values where N-i is a perfect square.

Bottom-up Dynamic Programming Algorihtm to Compute the Perfect Squares

The Bottom-up Dynamic Programming computes F(0), and then F(1) and then F(2) until we reach the value of F(N). The process is bottom-up.

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    @cache
    def numSquares(self, n: int) -> int:
        dp = [float("inf")] * (n + 1)
        dp[0] = 0
        for i in range(1, n + 1):
            j = 1
            while j * j <= i:
                dp[i] = min(dp[i], dp[i - j * j] + 1)
                j += 1
        return dp[-1] # or dp[n]

class Solution:
    @cache
    def numSquares(self, n: int) -> int:
        dp = [float("inf")] * (n + 1)
        dp[0] = 0
        for i in range(1, n + 1):
            j = 1
            while j * j <= i:
                dp[i] = min(dp[i], dp[i - j * j] + 1)
                j += 1
        return dp[-1] # or dp[n]

We are using an DP array to store the F(i) values where i is from 0 to N inclusive. The time complexity is same and space complexity is O(N).

See also: Find the Least Number Sums of Perfect Squares

–EOF (The Ultimate Computing & Technology Blog) —