Fewest Squares That Add Up
Print the fewest perfect squares that sum to n. Squares may be repeated.
12 -> 3 4 + 4 + 4
13 -> 2 4 + 9
Greedy fails, and 12 is the smallest case that shows it. Taking the largest
square that fits gives 9 + 1 + 1 + 1, four terms, while three fours do it in
three. Largest-first is a reasonable instinct and it is simply not true here.
The recurrence is the coin-change shape with the coin set fixed to the squares:
dp[0] = 0
dp[i] = 1 + min over j*j <= i of dp[i - j*j]
Filling i upwards means every dp[i - j*j] is already final when it is read,
which is what makes the bottom-up order valid.
Note the inner loop runs to sqrt(i), not to i, so the total work is the sum
of sqrt(i) over all i, about n * sqrt(n) / 1.5.
There is a classical result that the answer is always 1, 2, 3 or 4, never more, which makes a constant-time solution possible. The table is what an interview wants, and the theorem is worth knowing as a check rather than as the answer.