A square number is k * k for some whole k >= 1: 1, 4, 9, 16, 25, .... The same square may be used more than once.
Write fewest_squares(n: int) -> int that returns the smallest count of square numbers whose sum is exactly n.
fewest_squares(12) # 3 4 + 4 + 4 (9 + 1 + 1 + 1 would be 4)
fewest_squares(13) # 2 4 + 9
fewest_squares(16) # 1
fewest_squares(7) # 4 4 + 1 + 1 + 1
Constraints: 1 <= n <= 10^4.
Taking the biggest square that fits each time is wrong (see 12), and trying every way to split n is exponential. Aim for O(n·√n) time. A recursive version would nest up to 10,000 calls, past Python's default recursion limit, so work iteratively.
Show hint
the best answer for n is one square s plus the best answer for n - s. Work out every smaller total first, from 0 upwards.