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