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.
A perfect square is an integer p that can be represented as q^2 for some other integer q. For example, 9 is a perfect square
since 9 = 3^2. However, 8 isn't a perfect square.
Examples
Example 1:
Input: 12
Output: 3
Explanation:
12 = 4 + 4 + 4
Example 2:
Input: 13
Output: 2
Explanation:
13 = 4 + 9