12

1 4 9


build perfect squares up to n
12-9=3
3-1=2
2-1=1

12=9+1+1+1 -> 4
12=4+4+4 -> 3



1 -> 1  (1)
2 -> 2  (1+1)
3 -> 3  (1+1+1)
4 -> 1  (4)
5 -> 2  (4+1)
6 -> 3  (4+1+1)
7 -> 4	4+1+1+1 
8 -> 2	4+4



f(1) = 1
f(2) = f(1) + f(1) = 1+1=2

f(7) = f(4) + f(3) = 1+3=4
f(8) = f(4) + f(4) = 1+1=2
f(12) = f(8) + f(4) = 2+1=3

identify subproblems?

https://leetcode.com/problems/perfect-squares/discuss/696436/Python-Simple-DP-Solution

n=7
square_sums = [0,1,4] 
dp = [0, inf, inf, inf, inf, inf, inf, inf]

      0  1  2  3  4  5  6  7
dp = [0, 1, 2, 3, 1, 2, 3, 4]

dp = [0, 1, inf, inf, 1, inf, inf, inf]

i: 1->n
iter all squares
min( dp[i], dp[i-square] )




f(1)=1
f(2)=2
f(12)=





these are the candidates