Given an integer n, return the least number of perfect square numbers that sum to n. Each square can be used multiple times, so this is a classic unbounded knapsack minimization problem.
n = target sum
minimum number of perfect squares summing to n
Example 1:
Input:
n = 12
Output:
3
Explanation:
12 = 4 + 4 + 4.
Example 2:
Input:
n = 13
Output:
2
Explanation:
13 = 4 + 9.