407. 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.
Constraints - `1 ≤ n ≤ 10000`
Input
One line containing the integer n.
Output
Print the fewest perfect squares summing to n.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.