Perfect Squares

Problem

Given a positive integer n, find the smallest number of perfect squares (1, 4, 9, 16, ...) that add up to exactly n. The same square may be used more than once.

• n is a positive integer up to around ten thousand.

Examples

• n = 21 → 3, using 16 + 4 + 1. Note that 9 + 9 + 1 + 1 + 1 uses five squares and is worse.
• n = 18 → 2, using 9 + 9.
• n = 4 → 1. Four is itself a perfect square.

Hints

1. If you knew the answer for every smaller number, how would you build the answer for n from one of them plus a single square?
2. The "coins" here are the squares up to n. There are only about sqrt(n) of them.
3. Unbounded knapsack with minimization: fewest[i] = 1 + min(fewest[i - k*k] for k*k <= i). Equivalently, BFS from n where each edge subtracts a square.