Am I ready for Dynamic Programming?

A brief guide to getting started with dynamic programming.

I can recall a time when I regarded Dynamic Programming as an obscure optimization technique reserved for my technical superiors. I’m here to dispel any such thoughts and show you that, while it takes some time and practice to get quick at breaking down problems to fit a Dynamic Programming approach, it’s something you can start implementing in your problem solving easily starting today.

Steps:

1. Identify that your problem can be solved with Dynamic Programming.
2. Define problem state structure.
3. Define relationship between state values.
4. Cache your mapping between state keys and values (Tabulation or Memoization).

1. Is my problem a fit for Dynamic Programming?

The answer to this question can usually be found by answering two other question (…They’re breeding).

1. Overlapping Subproblems — Can my problem be broken down into a tree of smaller subproblems, with most branches containing equivalent subproblems to others?

2. Optimal Substructure — Can my problem be defined as a mathematical relationship between subproblems?

Let’s look at the problem of calculating nth fibonacci.

A simple recursive solution to this problem is:

// nth-fibonacci.ts
const nthFib = (n: number): number => {
  if (n <= 1) return n;
  return nthFib(n - 1) + nthFib(n - 2);
};

Here, we can observe the following tree of subproblems:

nthFib(5) === nthFib(4) + nthFib(3);
nthFib(4) === nthFib(3) + nthFib(2);
nthFib(3) === nthFib(2) + nthFib(1);
nthFib(2) === nthFib(1) + nthFib(0);

Overlapping Subproblems

Does the solution break the problem down into a tree of smaller subproblems, with most branches containing equivalent subproblems?

We call nthFib(3) twice, nthFib(2) thrice, and nthFib(1) 5 times. If that isn’t repeating subproblems, I don’t know what is.

Optimal Substructure

Does the solution define the problem as a mathematical relationship between subproblems?

nthFib(n - 1) + nthFib(n - 2) seems to fit the bill.

With these two questions answered affirmatively, we can say with confidence that Dynamic Programming is a fit to our problem.

2. What’s a suitable state expression?

And what do we mean by state, anyway?

Here, by state, we mean the information we’ll use to identify one subproblem from another. In our nth fibonacci problem, the n value is how we distinguish subproblems, so our state expression would be state(n). There can be a number of ways to identify subproblems, and it’s crucial to be diligent with this step to ensure you’ve identified an ideal state structure. Typically, you’ll want to yield to the state definition with the fewest parameters to reduce the space complexity of your state expression.

3. What is the mathematical relationship between our state values?

As discussed in step one, the answer to this question for nth fibonacci is state(n) === state(n-1) + state(n-2).

This step is not always so simple or obvious however. This is typically the most difficult part of solving a problem using Dynamic Programming, and it can require a lot of practice to hone your intuition. For a slightly more complex example walkthrough, check out GeeksForGeeks’ example here, and try to see if you can figure out the state relationship before looking at their explanation.

4. Cache? 💵 💵 💵

This should be the easiest step. We just need to store the state answers so that we can retrieve them from memory in constant time each time a state key is revisited. This can be achieved via memoization or tabulation.

Here is what a final solution for nth fibonacci using tabulation might look like:

const nthFib = (n: number): number => {
  const state = {};
  state[0] = 0;
  state[1] = 1;
  let i = 2;
  while (state[n] === undefined) {
    state[i] = state[i - 1] + state[i - 2];
    i++;
  }

  return state[n];
};

Conclusion

While it takes some practice to develop an intuition around how to solve problems quickly with Dynamic Programming, it’s a relatively accessible technique. I’m hopeful this intro has given you the tools to get started on your practice as you go about solving your problems. Much of this article is influenced by my reading of GeeksToGeeks’ breakdown. Go check their breakdown out for a deeper dive on some of the concepts: https://www.geeksforgeeks.org/solve-dynamic-programming-problem