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.
Unbounded coin change where the coins are the perfect squares below n. Every amount is reachable (1 is a square), so the answer always exists. Precomputing the square list and breaking once s > i keeps the inner loop tight.
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
Common pitfalls
Greedily taking the largest square
while n: n -= largest_square_below(n); count += 1
dp[i] = min(dp[i], dp[i - s] + 1)
Greedy fails on 12: it takes 9 then 1+1+1 for four terms, when 4+4+4 gives three. Coin systems only admit greedy under special conditions that perfect squares don't satisfy.
Recomputing squares inside the loop
for i in range(1, n+1):
for k in range(1, int(i**0.5)+1):
dp[i] = min(dp[i], dp[i - k*k] + 1)squares = [k * k for k in range(1, int(n ** 0.5) + 1)]
That's a square root and a multiplication per inner step. Building the list once turns the inner loop into plain array reads, and the break on s > i stops it early.
Initialising dp to 0 instead of infinity
dp = [0] * (n + 1)
dp = [0] + [float('inf')] * nmin against a stored 0 always returns 0, so every entry stays 0 and the answer is 0. Unreached states must start at infinity so the first real candidate wins; only dp[0] is genuinely zero.
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.