12 Dynamic Programming Interview Questions and Problems (SOLVED)

Dynamic programming is all about ordering your computations in a way that avoids recalculating duplicate work. More specifically, Dynamic Programming is a technique used to avoid computing multiple times the same subproblem in a recursive algorithm. DP algorithms could be implemented with recursion, but they don't have to be.

With dynamic programming, you store your results in some sort of table generally. When you need the answer to a problem, you reference the table and see if you already know what it is. If not, you use the data in your table to give yourself a stepping stone towards the answer.

There are two approaches to apply Dynamic Programming:

• The top-down or memoization. When the recursion does a lot of unecessary calculation, an easy way to solve this is to cache the results and to check before executing the call if the result is already in the cache.
• The bottom-up or tabulation approach. A better way to do this is to get rid of the recursion all-together by evaluating the results in the right order and building the array as we iterate. The partial results are available when needed if the iteration is done in the right order.

TOP of the tree
fib(4)
 fib(3)...................... + fib(2)
  fib(2)......... + fib(1)       fib(1)........... + fib(0)
   fib(1) + fib(0)   fib(1)       fib(1)              fib(0)
    fib(1)   fib(0)
BOTTOM of the tree

• Memoization is when you store previous results of a function call (a real function always returns the same thing, given the same inputs). It doesn't make a difference for algorithmic complexity before the results are stored.
• Recursion is the method of a function calling itself, usually with a smaller dataset. Since most recursive functions can be converted to similar iterative functions, this doesn't make a difference for algorithmic complexity either.
• Dynamic programming is the process of solving easier-to-solve sub-problems and building up the answer from that. Most DP algorithms will be in the running times between a Greedy algorithm (if one exists) and an exponential (enumerate all possibilities and find the best one) algorithm.
  • DP algorithms could be implemented with recursion, but they don't have to be.
  • DP algorithms can't be sped up by memoization, since each sub-problem is only ever solved (or the "solve" function called) once.

Pros:

• Memoization is very easy to code (you can generally* write a "memoizer" annotation or wrapper function that automatically does it for you), and should be your first line of approach. It feels more natural. You can take a recursive function and memoize it by a mechanical process (first lookup answer in cache and return it if possible, otherwise compute it recursively and then before returning, you save the calculation in the cache for future use), whereas doing bottom up dynamic programming requires you to encode an order in which solutions are calculated.
• Top-down only solves sub-problems used by your solution whereas bottom-up might waste time on redundant sub-problems.

Cons:

• With memoization, if the tree is very deep (e.g. fib(106)), you will run out of stack space, because each delayed computation must be put on the stack, and you will have 106 of them.

The key idea of DP is to save answers of overlapping smaller sub-problems to avoid recomputation. For that:

• An instance is solved using the solutions for smaller instances.
• The solutions for a smaller instance might be needed multiple times, so store their results in a table.
• Thus each smaller instance is solved only once.
• Additional space is used to save time.

• Let's assume the indices of the array are from 0 to N - 1.
• Let's define DP[i] to be the length of the LIS (Longest increasing subsequence) which is ending at element with index i.

DP[0] = 1; // length of LIS for the first element is always 1
int maxLength = 1;

• To compute DP[i] for each i > 0 we look at all indices j < i and check both:

  • if DP[j] + 1 > DP[i] and
  • array[j] < array[i] (we want it to be increasing).

  • If this is true we can update the current optimum for DP[i].

    for (int i = 1; i < N; i++)
       {
          DP[i] = 1;
          prev[i] = -1;
    
          for (int j = i - 1; j >= 0; j--)
             if (DP[j] + 1 > DP[i] && array[j] < array[i])
             {
                DP[i] = DP[j] + 1;
                prev[i] = j;
             }
    
          if (DP[i] > maxLength)
          {
             bestEnd = i;
             maxLength = DP[i];
          }
       }

• To find the global optimum for the array you can take the maximum value from DP [0...N - 1]
• Use the array prev to be able later to find the actual sequence not only its length. Just go back recursively from bestEnd in a loop using prev[bestEnd]. The -1 value is a sign to stop.

The following would be considered DP, but without recursion (using bottom-up or tabulation DP approach).

int fibresult[N];

void setup_fib()
{
    fibresult[0] = 1;
    fibresult[1] = 1;
    for (int i = 2; i < N; i++)
       fibresult[i] = fibresult[i-1] + fibresult[i-2];
}

int fib(int x) { return fibresult[x]; }

This way may be described as "eager", "precaching" or "iterative". Its faster overall but we have to manually figure out the order the subproblems need to be calculated in. This is easy for fibonacci, but for more complex DP problems it gets harder, and so we fall back to the lazy recursive method if it is fast enough.

Pros:

• If you are doing an extremely complicated problems, you might have no choice but to do tabulation (or at least take a more active role in steering the memoization where you want it to go). Also if you are in a situation where optimization is absolutely critical and you must optimize, tabulation will allow you to do optimizations which memoization would not otherwise let you do in a sane way.
  • Why? Because with memoization, if the tree is very deep (e.g. fib(10^6)), you will run out of stack space, because each delayed computation must be put on the stack, and you will have 10^6 of them.
• In many applications the bottom-up approach is slightly faster because of the overhead of recursive calls.

Cons:

• The downside of tabulation is that you have to come up with an ordering. You must pick, ahead of time, the exact order in which you will do your computations.
• Top-down only solves sub-problems used by your solution whereas bottom-up might waste time on redundant sub-problems.

Dynamic programming is an extension of Divide and Conquer paradigm.

• They both work by recursively breaking down a problem into two or more sub-problems. The solutions to the sub-problems are then combined to give a solution to the original problem.
• In Divide and conquer the sub-problems are independent of each other. Mergesort is a classic example of divide and conquer. The main difference between this example and the Fibonacci example is that in a mergesort, the division can (theoretically) be arbitrary, and no matter how you slice it up, you are still merging and sorting.
• In dynamic programming the sub-problem are not independent. So to calculate new Fib number you have to know two previous values. For Merge sort you don't need to know the sorting order of previously sorted sub-array to sort another one.
• Dynamic programming approach may be applied to the problem only if the problem has certain restrictions or prerequisites:
• Optimal substructure — optimal solution can be constructed from optimal solutions of its subproblems
• Overlapping sub-problems — problem can be broken down into subproblems which are reused several times or a recursive algorithm for the problem solves the same subproblem over and over rather than always generating new subproblems.
• Dynamic programming approach extends divide and conquer approach with two techniques:
  • memoization (top-down cache filling)
• tabulation (bottom-up cache filling)

Two things to consider when deciding which algorithm to use

1. Time Complexity. Both approaches have the same time complexity in general, but because for loop is cheaper than recursive function calls, bottom-up can be faster if measured in machine time.
2. Space Complexity. (without considering extra call stack allocations during top-down) Usually both approaches need to build a table for all sub-solutions, but bottom-up is following a topological order, its cost of auxiliary space can be sometimes reduced to the size of problem's immediate dependencies. For example: fibonacci(n) = fibonacci(n-1) + fibonacci(n-2), we only need to store the past two calculations

That being said, bottom-up is not always the best choice, I will try to illustrate with examples:

1. Top-down only solves sub-problems used by your solution whereas bottom-up might waste time on redundant sub-problems. A silly example would be 0-1 knapsack with 1 item...run time difference is O(1) vs O(weight)
2. you might need to perform extra work to get topological order for bottm-up. In Longest Increasing Path in Matrix if we want to do sub-problems after their dependencies, we would have to sort all entries of the matrix in descending order, that's extra nmlog(nm) pre-processing time before DP