I have been reading up on dynamic programming lately. Would like to hear from someone who started from scratch and now is pretty good at identifying and solving DP problems. I am struggling in identifying these problems as DP and framing a concise solution.
I have gone through most of the beginner DP problems and MIT resources etc
Best Answer
I come from a physics background, and thus, lots of maths. I find easy to spot problems well suited to recursive/dynamic programming solutions by finding similarities with proof by induction.
In proof by induction you have two parts:
In recursive programming/dynamic programming:
So, as others answered, it is a matter of experience and picking the hints, but you can re-use other skills to guide you. After that, you need to always have the two parts which I mentioned: if you don't, then it won't work.
For example, to generate all the permutations of a set: