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.