Problem - Perfect Squares (Third problem)

Given a positive integer $n$, find the minimum number of perfect square numbers that sum to $n$. For example, $n = 12$ can be written as $4 + 4 + 4$ (three squares) or $9 + 1 + 1 + 1$ (four squares). The answer is $3$.

This is a dynamic programming problem, but logarithms appear when computing perfect squares. How many perfect squares are there up to $n$? About $\sqrt{n}$, and $\log_2(\sqrt{n}) = \frac{1}{2} \log_2(n)$.

Before reading the solution, think about this: how would you find all perfect squares up to $n$? And how does the logarithm relate to the number of bits in $n$?