How to identify a problem as being suitable for dynamic programming

algorithmsdynamic programming

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:

  • you prove that if something is true for iteration N, it is also true for iteration N+1
  • you prove that it is true for iteration 1

In recursive programming/dynamic programming:

  • you identify an exit condition (for example, you hard wire the solution for iteration 1)
  • you calculate solution for iteration N given the solution for iteration N-1

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:

  • exit condition: if you only have one element, return it
  • recursion: the permutations of a set of N items are the N sets of permutations you get by choosing each element and combining the with all the N-1 sets of (many) permutations of the subset you get by removing the element.
Related Topic