Intuition
The tempting shortcut is greedy: grab the largest perfect square below n and recurse on the remainder. It fails on 12 -- greedy takes 9, then is stuck adding 1+1+1 for a total of four squares, but 4+4+4 uses only three. The largest square is not always part of an optimal decomposition. The fix is to treat this as unbounded knapsack: for every amount from 1 to n, try EVERY perfect square not exceeding it and keep the option that leaves the cheapest remainder. The invariant: dp[i] is the fewest squares that sum to i, and it is only correct once every candidate square has been considered at every amount, not just the biggest one.
Approach
Precompute candidates
Build the list of perfect squares (1, 4, 9, ...) up to n; these are the only pieces the sum can be built from.
Try every square at every amount
dp[0] = 0. For each amount i from 1 to n, scan every square s <= i and take dp[i] = min over all such s of (1 + dp[i - s]). This is unbounded knapsack -- each square can be reused any number of times, and nothing is skipped just because it is not the largest.
Final answer
dp[n] holds the minimum count. Because every amount considers all candidate squares, the greedy failure mode (locking in the biggest square too early) never occurs.
Solution & live demo
Edge cases
dp[n] = 1, found directly when the square equal to n is tried.
dp[12] correctly resolves to 3 (4+4+4), not the greedy 4 (9+1+1+1).
dp[1] = 1 trivially, using the square 1 itself.
The DP still checks every square size at every amount, so it cannot get trapped by an early bad choice the way greedy does.