Fewest perfect squares that sum to n

Given a positive integer n, return the minimum number of perfect squares (1, 4, 9, 16, ...) that sum to exactly n. You may reuse a square as many times as you like.

n = 12  ->  3     # 4 + 4 + 4
n = 13  ->  2     # 4 + 9
n = 1   ->  1     # 1

Return the fewest squares. Target $O(n\sqrt{n})$.