Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
1+2^2+3^2
it's a DP problem or dfs?
n -> sqrt(n)? nope... it may not be the best like 12 = not 9 + 1 + 1 + 1 is 4 + 4 + 4
I suddenly want to use python to solve this problem.
I need to chage it to DP...
AC...yes just transfer the dfs to DP.