Fewest squares that sum to n: build a table up from zero, trying every square that fits. It's Coin Change with squares as coins.
▼The problem
LeetCode 279 (Medium). Given an integer n, return the least number of perfect squares (1, 4, 9, 16, ...) that sum to n.
Examples (LeetCode's): n = 12 → 3 (4 + 4 + 4) and n = 13 → 2 (4 + 9).
The solution
from math import inf, isqrt
def num_squares(n):
squares = [k * k for k in range(1, isqrt(n) + 1)]
dp = [0] + [inf] * n
for i in range(1, n + 1):
for s in squares:
if s > i:
break
dp[i] = min(dp[i], dp[i - s] + 1)
return dp[n]Transcript
Perfect Squares. Given a number n, return the least number of perfect squares, like one, four, nine or sixteen, that add up to n.
For twelve, the answer is three: four plus four plus four. For thirteen, it's two: four plus nine. But grabbing the biggest square first fails on twelve: nine plus one plus one plus one is four squares, not three.
The direct way: try every square, then solve what's left. Twelve tries eleven, eight and three, and each of those branches again. Three alone gets solved eleven times: a hundred and four calls, growing exponentially.
The key idea: build up from zero. D P of zero is zero. For each i, try every square that fits; the best is one plus D P of i minus that square. It's Coin Change, with squares as the coins.
In code, fill the table with infinity, except zero. For each i, loop over the squares up to i, and keep the smallest one plus D P of i minus the square. Return the last entry.
For twelve: one, two and three need that many ones. Four is a square: one. Seven needs four. Eight is two fours, and nine is one. Then twelve tries eleven, eight and three. Eight gives two, plus one is three.
Each of n values tries up to root n squares: n root n time, and n space. A breadth first search over remainders also works.
Start from zero, try every square, keep the fewest. That's Perfect Squares.