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? firstname.lastname@example.org