279. Perfect Squares

-
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum 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.
---
Intuition

Naive approach
Find the max perfect square less than number
while (target - max perfect square less than number > 0)
  target = target - max perfect square
  ans ++

This does not work all the time
Ex - 18 = 16 + 1 + 1 => 3 .. per above approach - incorrect
18 = 9 + 9 => 2 .. correct approach

So we need to perform searches on all perfect number

F(Target) = 1 + min (F(target - perfect 1), F(target - perfect 2).....

Some of these F(target - perfect n) calls are repeated, memoize them
---
Related problems
coin-change
minimum-cost-for-tickets