How do you identify a problem as being suitable for dynamic programming?

Question

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

Answer 1

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.

Answer 2

Most dynamic programming problems can be solved via memoization. Memoization is normally both more intuitive and easier to code. You may find it helpful to think in terms of memoization instead of DP.

It's usually easier to intuit whether a problem is well-suited towards memoization (the steps are the same as Slivvz's answer, but I think the mental shift is a little shorter). However, once you've solved a problem via memoization, you can examine how your memo cache is being filled and then fill it in order, without recursion...which changes your algorithm to a dynamic programming algorithm.

See also
Dynamic programming and memoization: bottom-up vs top-down approaches.

Answer 3

Dynamic programming is definitionally about two things:

1. Optimal substructure
   Larger solutions can be derived from smaller solutions; solving is not bidirectional.

2. Overlapping subproblems
   The small solutions will be reused many times. If the subproblems don’t overlap at all, then you don’t benefit from DP/memoisation; what you have is divide and conquer instead.

The general approach to DP problems is:

• Write a naïve recursive or iterative version that works.

• Notice that the function is doing redundant work.

• Find a way to avoid doing that redundant work, often by memoisation.

Answer 4

I'd never implemented a single dynamic programming solver - my background is applied maths/physics/numerical computing, not CS - until a few years ago when I started doing Project Euler problems. The DP-solvable problems there (e.g 76, 158, 161, 242, but there are many more) turned out to be pretty much my favourite kind. You do definitely get better at spotting when it'll be a useful technique: basically look for things which seem like they could be solved by some sort of recursive, divide-and-conquer approach where it's also possible to tame the explosion of pathways needing to be explored by recognising recurring subproblems and reusing the previously computed results; being able to identify the minimal state vector to memoise on - and what irrelevant "history" can be erased - is the crucial step.

Answer 5

Here are how I do it:

1. Choose a small sample size (eg 6th Fibonacci number).
2. Write the solution on paper (draw a binary tree, tabulation, etc).
3. Check if there are any similar nodes.

With practice, you will develop an intuition for recognizing DP problems.