Perfect Squares - The Insight (DP with square roots)

Define $dp[i]$ as the minimum number of perfect squares that sum to $i$. You want $dp[n]$.

For each $i$, try subtracting all perfect squares $j^2 \leq i$. Then $dp[i] = 1 + \min(dp[i - j^2])$ for all valid $j$. The base case is $dp[0] = 0$.

How many perfect squares $j^2 \leq i$ are there? About $\sqrt{i}$. So for each $i$, you do $O(\sqrt{i})$ work. Total time: $O(n \sqrt{n})$.