How to prepare for Dynamic Programming Questions

The most difficult problems in Coding competitions and interviews of companies like Google, Microsoft etc. are from Dynamic Programming. DP as an approach to problem solving is discussed in almost all algorithm books.

But, in most of the books, DP, as a concept is lost behind the difficult problems. For example, in one of the best algorithm books, Cormen, chapter of dynamic programming discuss complex examples like Matrix chain multiplication. Student get more absorbed in solving the complex problem rather than getting into the crux of the concept.

I think following steps may help in approaching a complex DP problem:

1. Master Recursion

The logic of DP and recursion is usually same. Recursion is relatively easy to develop solution. DP usually use the same logic (from recursion) and change it to solve the problem bottom-up. You can read the sample chapter of my book on recursion at the below link: https://notionpress.com/read/dynamic-programming-for-coding-interviews

2. Decide on the cache

DP problems usually demonstrate optimal substructure property. It literally means that solution of a larger problem requires us to solve smaller problem of the same type (hence recursion was a good tool).

Recursion, stores the intermediate results in the function call stack. Since we are not using recursion, in most cases, we end up using a cache to store the intermediate results. This cache is usually an array. In most cases, if there are two dimensions in the problem (eg. if we are talking about a grid then there are two dimensions along x and y axis).

3. Solve bottom up

There is a cost associated with solving a problem in top-down (using either recursion or memoization). DP reduce that cost by computing the problem in a bottom-up manner. Before solving the problem using DP or before even learning DP approach, we must be well informed of the cost that we are going to reduce. I wanted to compute 80^th term of the Fibonacci series. I wrote the rampant recursive function,

int fib(int n){
   return (1==n || 2==n) ? 1 : fib(n-1) + fib(n-2);
}

and waited for the result. I wait… and wait… and wait… With an 8GB RAM and an Intel i5 CPU, why is it taking so long? I terminated the process and tried computing the 40^th term. It took about a second.

I put a check and was shocked to find that the above recursive function was called 204,668,309 times while computing the 40^th term. More than 200 million times? Is it reporting function calls or scam of some government?

The Dynamic Programming solution computes 100^th Fibonacci term in less than fraction of a second, with a single function call, taking linear time and constant extra memory. A recursive solution, usually, neither pass all test cases in a coding competition, nor does it impress the interviewer in an interview of company like Google, Microsoft, etc.

The most difficult questions asked in competitions and interviews, are from dynamic programming. This book takes Dynamic Programming head-on. It first explain the concepts with simple examples and then deep dives into complex DP problems.

4. Practice, Practice and Practice

As they say, "Do not practice until you get it right, but keep practicing until you can't get it wrong." Once you understand the concept, then search the internet, There are lot of questions available online. Apply your understanding on each question. It's not a good practice to see the solution and remember it from the internet.

Whether it is a competition or an interview, chances are that you will get a question, that you have not done till now. Only, if you are hands-on with the concept, you will be able to solve it.

While solving any question, I suggest everyone to also go thru the not-so-good solutions. I usually recommend to try all the three solutions for a DP problem:

• Recursive
• Memoized
• Bottom-up Dynamic Programming

It helps us appreciate the benefits of DP more by comparing it with not-so-optimized solutions.