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

Try it yourself

Solution

←
↑TA πŸ‘¨β€πŸ«