LeetCode 279 · Recursion · DP

Perfect Squares, explained with a picture

Building a number from square tiles.

Recursion · DP
▶ Watch it step by step

The problem

Find the fewest perfect squares (1, 4, 9, 16, …) that add up to n.

Input:  12
Output: 3   (4 + 4 + 4)

Picture it

Picture building the number from square tiles. Fill boxes 0 … n with the fewest tiles needed. For box x, try every square s ≤ x: one tile s plus the best for x − s.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

dp[x] = 1 + min(dp[x − s²]). O(n√n).

Python solution

def num_squares(n):
    dp = [0] + [inf] * n         # fewest squares that sum to i
    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[n]

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from math import inf

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.