If there’s one topic that my readers seem to struggle with across the board, it’s dynamic programming.

I get it. Dynamic programming seems mysterious and inscrutable. It especially doesn’t help when you go on Leetcode to look at the solutions and someone has come up with this beautiful code that you could never replicate on your own.

The thing is, though, that dynamic programming doesn’t have to be a complete enigma. If you have the right, structured approach you can find the solution to any dynamic programming problem without breaking a sweat.

This is why I wrote Dynamic Programming for Interviews. This ebook not only introduces the FAST method for solving any dynamic programming interview question, but it goes through 5 different examples in detail to show you exactly how to apply the fast method.

This article is an excerpt from the book describing how the FAST method of solving dynamic programming problems works. After reading this article, make sure that you download the ebook HERE to learn by example how you can apply the FAST method during your interviews.

The FAST method

The most successful interviewees are those who have developed a repeatable strategy to succeed. This is especially true for dynamic programming. This is the reason for the development of the FAST method.

There are four steps in the FAST method:

1. First solution
2. Analyze the first solution
3. Identify the Subproblems
4. Turn the solution around

By following these four steps, it is easy to come up with an optimal dynamic solution for almost any problem.

First solution

This is an important step for any interview question but is particularly important for dynamic programming. This step finds the first possible solution. This solution will be brute force and recursive. The goal is to solve the problem without concern for efficiency. It means that if you need to find the biggest/smallest/longest/shortest something, you should write code that goes through every possibility and then compares them all to find the best one.

Your solution must also meet these restrictions:

• The recursive calls must be self-contained. That means no global variables.
• You cannot do tail recursion. Your solution must compute the results to each subproblem and then combine them afterwards.
• Do not pass in unnecessary variables. Eg. If you can count the depth of your recursion as you return, don’t pass a count variable into your recursive function.
  

Once you’ve gone through a couple problems, you will likely see how this solution looks almost the same every time.

Analyze the first solution

In this step, we will analyze the first solution that you came up with. This involves determining the time and space complexity of your first solution and asking whether there is obvious room for improvement.
As part of the analytical process, we need to ask whether the first solution fits our rules for problems with dynamic solutions:

• Does it have an optimal substructure? Since our solution’s recursive, then there is a strong likelihood that it meets this criteria. If we are recursively solving subproblems of the same problem, then we know that our substructure is optimal, otherwise our algorithm wouldn’t work.
• Are there overlapping subproblems? This can be more difficult to determine because it doesn’t always present itself with small examples. It may be necessary to try a medium-sized test case. This will enable you to see if you end up calling the same function with the same input multiple times.

Find the Subproblems

If our solution can be made dynamic, the exact subproblems to memoize must be codified. This step requires us to discover the high-level meaning of the subproblems. This will make it easier to understand the solution later. Our recursive solution can be made dynamic by caching the values. This top-down solution facilitates a better understanding of the subproblems which is useful for the next step.

Turn the solution around

We now have a top-down solution. This is fine and it would be possible to stop here. However, sometimes it is better to flip it around and to get a bottom up solution instead. Since we understand our subproblems, we will do that. This involves writing a completely different function (without modifying the existing code). This will iteratively compute the results of successive subproblems, until our desired result is reached.

The following sample problems use the FAST method to arrive at the solutions. By going through the examples, it will help you to understand how each of these steps is applied.