Dynamic Programming: The Framework | by Fernando López | Oct, 2022

What You Need to Know for Your Coding Interview

One of the most challenging topics in a coding interview is dynamic programming. Especially in the identification, approach, and development of a problem as an optimization task with dynamic programming.

In this blog, we are going to see the keys to identifying when a problem can be solved with dynamic programming and how to propose a solution step by step. Are you ready? Let’s go for it!

The dynamic programming paradigm refers to an optimization process where it is intended to explore all possible solutions efficiently until the optimal structure is found.

Commonly, a dynamic programming problem in its approach requires calculating the maximum or minimum of “something”, the different possibilities of doing “something”, the resulting value of a process in the state k, etc.

For example, what is the nth number of the Fibonacci series? Finding the nthnumber of the Fibonacci series turns out to be a dynamic programming problem because, in its nature, the nth number is determined by the numbers n-1and n-2which in turn are determined by n-2and n-3as well as n-3and n-4respectively. In other words, to find the solution for the state k, we need to know the solution for the previous k-1 states whose solutions are recursively related.

In Figure 2we can see a graphical representation of the dependence on recurring relationships of the Fibonacci series.

It is important to mention that the approach of a solution based on dynamic programming can be confused with a solution based on the divide and conquer technique. The difference is that solutions based on divide and conquer do not represent a recursive dependency relationship in contrast to a dynamic programming solution.

In a nutshell, the keys to identifying if your code interview problem can be solved with dynamic programming are:

• Identify if the problem can be broken down into sub-problems (thinking about what the base case would be like would be key at this point).
• Identifies if there is any recurrent dependency relationship between each subproblem (E.g. if the solution of a subproblem has impacts on the solution of the consequent subproblem).
• Lean on key phrases: find the maximum or minimum of “something”, find the n possibilities to do “something” under certain restrictions, etc.

Once you have identified that the problem at hand can be addressed as dynamic programming, you will now need a strategy to formulate and develop the solution. In the next section, we will see three essential components to propose and develop your solution.

Let’s go for it!

The essential components to develop a solution based on dynamic programming are:

1. A function or data structure that models the recurrence relationship between each of the states.
2. Memoization & Tabulation.
3. Base cases

Let’s look at each of the elements in detail.

1. The function or data structure

The exploration of all the states requires a data structure that allows the tracking of the solutions for each one of them. Commonly, an array for iterative scanning (bottom-up-based approach) or a function for recursive scanning (top-down-based approach) is used.

Code snippet 1 shows the comparison between an iterative and a recursive relationship function.

1.a. Top-down & Bottom-up based approaches

The top-down approach implies a recursion function that approaches the problem from back to front. On the other hand, the bottom-upapproach uses a data structure (commonly an array) for state dependency modeling iteratively.

The top-down approach starts from the state n until reaching the base case and the bottom-up approach starts from the base case until reaching the case n.

2. Memoization & Tabulation

Memoization and Tabulation refer to the use of a data structure to keep track and trace the solutions of each state.

Memoization is commonly used with the top-down approach where the most commonly used data structure is a hashmap. Tabulation is commonly used with the bottom-up approach where the data structure is an array. Both strategies allow for keeping track of the solutions to the subproblems for each of the states.

3. Base case

The base case determines the start of the process (for the bottom-up approach) or the end (for the top-down approach).

Basically, the base case is that case that can be defined without the need to apply dynamic programming, in other words, it is the case from which we start or the case that we will eventually reach.

The base cases for the top-down and bottom-upapproaches to the Fibonacci series are noted in code snippet 2.

Now that we know how to identify if a problem can be addressed with dynamic programming and what are the essential components to build a solution, let’s move on to an example where we apply what we have learned so far.

Let’s go for it!

Before we start with the solution, let’s go step by step. First, we need to identify if this problem can be solved with dynamic programming, so let’s analyze how the Fibonacci series behaves.

As we can see in Figure 3, for each number iit is required to know, in advance, the values of numbers i-1and i-2, that is, the problem can be broken down into sub-problems, where these sub-problems have a dependency relationship in their respective solutions. Therefore, we can say that this challenge can be approached as a dynamic programming problem.

Now let’s apply the framework we saw in the previous section. The first component refers to detecting the function or data structure that will maintain the solution for each of the states, where this function can address a bottom-up and top-downapproach.

For explanatory purposes, let’s address both approaches. For the bottom-up approach, we will need an iterative function, and for the top-down approach, we will need a recursive function.

In code snippet X the prototype of both approaches is shown.

Now we need to consider memoization or tabulation. In this case and for explanatory purposes, we are going to address both. In the case of the bottom-up approach, we are going to use tabulation, that is, an array that will contain the solutions for each of the states, and for the top-down approach, we are going to use memoization, that is, a hashmap that will contain the solution of each state.

In code snippet 4we can see the implementation of tabulation and memoization for each of the approaches.

Finally, we need to address the base case. The bottom-up approach takes the base case as a starting point until the state kis reached, and the top-down approach starts from the case kand stops until the base case is found.

The base case for the bottom-up and top-down approach, respectively, is shown in code snippet 5.

And that’s it. The problem of finding the nthnumber in the Fibonacci sequence has been developed with a solution based on the dynamic programming paradigm.

In this blog we saw how to identify if a problem can be addressed with dynamic programming and, if so, what are components to consider to propose and develop a solution. Finally, we show an example of how to build a dynamic programming-based solution to the problem of finding the Nth number of the Fibonacci sequence.

What You Need to Know for Your Coding Interview

One of the most challenging topics in a coding interview is dynamic programming. Especially in the identification, approach, and development of a problem as an optimization task with dynamic programming.

In this blog, we are going to see the keys to identifying when a problem can be solved with dynamic programming and how to propose a solution step by step. Are you ready? Let’s go for it!

The dynamic programming paradigm refers to an optimization process where it is intended to explore all possible solutions efficiently until the optimal structure is found.

Commonly, a dynamic programming problem in its approach requires calculating the maximum or minimum of “something”, the different possibilities of doing “something”, the resulting value of a process in the state k, etc.

For example, what is the nth number of the Fibonacci series? Finding the nthnumber of the Fibonacci series turns out to be a dynamic programming problem because, in its nature, the nth number is determined by the numbers n-1and n-2which in turn are determined by n-2and n-3as well as n-3and n-4respectively. In other words, to find the solution for the state k, we need to know the solution for the previous k-1 states whose solutions are recursively related.

In Figure 2we can see a graphical representation of the dependence on recurring relationships of the Fibonacci series.

It is important to mention that the approach of a solution based on dynamic programming can be confused with a solution based on the divide and conquer technique. The difference is that solutions based on divide and conquer do not represent a recursive dependency relationship in contrast to a dynamic programming solution.

In a nutshell, the keys to identifying if your code interview problem can be solved with dynamic programming are:

• Identify if the problem can be broken down into sub-problems (thinking about what the base case would be like would be key at this point).
• Identifies if there is any recurrent dependency relationship between each subproblem (E.g. if the solution of a subproblem has impacts on the solution of the consequent subproblem).
• Lean on key phrases: find the maximum or minimum of “something”, find the n possibilities to do “something” under certain restrictions, etc.

Once you have identified that the problem at hand can be addressed as dynamic programming, you will now need a strategy to formulate and develop the solution. In the next section, we will see three essential components to propose and develop your solution.

Let’s go for it!

The essential components to develop a solution based on dynamic programming are:

1. A function or data structure that models the recurrence relationship between each of the states.
2. Memoization & Tabulation.
3. Base cases

Let’s look at each of the elements in detail.

1. The function or data structure

The exploration of all the states requires a data structure that allows the tracking of the solutions for each one of them. Commonly, an array for iterative scanning (bottom-up-based approach) or a function for recursive scanning (top-down-based approach) is used.

Code snippet 1 shows the comparison between an iterative and a recursive relationship function.

1.a. Top-down & Bottom-up based approaches

The top-down approach implies a recursion function that approaches the problem from back to front. On the other hand, the bottom-upapproach uses a data structure (commonly an array) for state dependency modeling iteratively.

The top-down approach starts from the state n until reaching the base case and the bottom-up approach starts from the base case until reaching the case n.

2. Memoization & Tabulation

Memoization and Tabulation refer to the use of a data structure to keep track and trace the solutions of each state.

Memoization is commonly used with the top-down approach where the most commonly used data structure is a hashmap. Tabulation is commonly used with the bottom-up approach where the data structure is an array. Both strategies allow for keeping track of the solutions to the subproblems for each of the states.

3. Base case

The base case determines the start of the process (for the bottom-up approach) or the end (for the top-down approach).

Basically, the base case is that case that can be defined without the need to apply dynamic programming, in other words, it is the case from which we start or the case that we will eventually reach.

The base cases for the top-down and bottom-upapproaches to the Fibonacci series are noted in code snippet 2.

Now that we know how to identify if a problem can be addressed with dynamic programming and what are the essential components to build a solution, let’s move on to an example where we apply what we have learned so far.

Let’s go for it!

Before we start with the solution, let’s go step by step. First, we need to identify if this problem can be solved with dynamic programming, so let’s analyze how the Fibonacci series behaves.

As we can see in Figure 3, for each number iit is required to know, in advance, the values of numbers i-1and i-2, that is, the problem can be broken down into sub-problems, where these sub-problems have a dependency relationship in their respective solutions. Therefore, we can say that this challenge can be approached as a dynamic programming problem.

Now let’s apply the framework we saw in the previous section. The first component refers to detecting the function or data structure that will maintain the solution for each of the states, where this function can address a bottom-up and top-downapproach.

For explanatory purposes, let’s address both approaches. For the bottom-up approach, we will need an iterative function, and for the top-down approach, we will need a recursive function.

In code snippet X the prototype of both approaches is shown.

Now we need to consider memoization or tabulation. In this case and for explanatory purposes, we are going to address both. In the case of the bottom-up approach, we are going to use tabulation, that is, an array that will contain the solutions for each of the states, and for the top-down approach, we are going to use memoization, that is, a hashmap that will contain the solution of each state.

In code snippet 4we can see the implementation of tabulation and memoization for each of the approaches.

Finally, we need to address the base case. The bottom-up approach takes the base case as a starting point until the state kis reached, and the top-down approach starts from the case kand stops until the base case is found.

The base case for the bottom-up and top-down approach, respectively, is shown in code snippet 5.

And that’s it. The problem of finding the nthnumber in the Fibonacci sequence has been developed with a solution based on the dynamic programming paradigm.

In this blog we saw how to identify if a problem can be addressed with dynamic programming and, if so, what are components to consider to propose and develop a solution. Finally, we show an example of how to build a dynamic programming-based solution to the problem of finding the Nth number of the Fibonacci sequence.