Perfect squares sum

Given a positive integer n (1 <= n <= 1e6), return the least number of perfect squares (1, 4, 9, 16, ...) that sum to n. For example 12 = 4 + 4 + 4 needs 3, and 13 = 4 + 9 needs 2. An O(sqrt(n)) number-theoretic solution exists; the O(n*sqrt(n)) DP also works but is slower.