We could solve it by Theorem on the sum of four squares, I wonder how to solve it by DP? If you know, please help me, thank you!
Well...
For n=72... what are the possible squares you can take?
You can take 64,49,36,25...4,1 . So what's the best result for 72?
The best result Best(72)=min(Best(72-64),Best(72-49),Best(72-36), ... Best(72-1))+1;
Now whats the base cases? U see, for all square numbers, u can take it in one go.
So Best(1)=Best(4)=Best(9)=Best(16) ... = 1
Its a top down approach.
I hope u got the idea...
Goodluck.
Btw, I'm wondering how u solved by Theorem on the sum of four squares. Can u send your code to my mail please?
ealham86@gmail.com
