Deciding on Sub-Problems for Dynamic Programming

Question Detail: 

I have used the technique of dynamic programming multiple times however today a friend asked me how I go about defining my sub-problems, I realized I had no way of providing an objective formal answer. How do you formally define a sub-problem for a problem that you would solve using dynamic programming?

Asked By : jozefg

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/645

Answered By : Suresh

The principle of dynamic programming is to think top-down (i.e recursively) but solve bottom up. So a good strategy for designing a DP is to formulate the problem recursively and generate sub-problems that way.