Perfect Squares

Prereq: Knapsack Intro

Given a number that is less than 10^5 determine the smallest amount of perfect squares needed to sum to a particular number? The same number can be used multiple times.

Examples

Example 1:
Input: 12
Output: 3
Explanation:

12 = 4 + 4 + 4

Example 2:
Input: 13
Output: 2
Explanation:

13 = 4 + 9

Try it yourself

Solution