Perfect Squares
Prereq: Knapsack Intro
Given an integer n, determine the smallest number of perfect squares that sum to n. The same square may be used multiple times.
A perfect square is an integer p that can be written as q^2 for some integer q. For example, 9 is a perfect square since 9 = 3^2, while 8 is not.
Input & Output
Input
n — the number to write as a sum of perfect squares
Output
the smallest count of perfect squares that sum to n
Example
Input
n = 12
Output
3
Explanation
12 = 4 + 4 + 4 uses three squares. No pair of squares sums to 12, so three is the minimum.
Example
Input
n = 13
Output
2
Explanation
13 = 4 + 9. Taking the largest square first would give 13 = 9 + 1 + 1 + 1, four squares, so the greedy choice is not the minimum here.
Constraints
1 <= n <= 10^4