Perfect Squares - DP Insight

Let $dp[i]$ be the minimum number of perfect squares that sum to $i$. Base case: $dp[0] = 0$ (you need zero squares to make zero).

For each $i$ from $1$ to $n$, try all perfect squares $k^2 \leq i$. Compute $dp[i] = \min(dp[i], dp[i - k^2] + 1)$.

This says: to make $i$, take a perfect square $k^2$ and add it to the optimal solution for $i - k^2$. The answer is $dp[n]$.