X

Explore your training options in 10 minutes

# Dynamic Programming: An Introduction

Christina Kopecky - September 12, 2020

In computer science there are several ways that describe the approach to solving an algorithm. Greedy, Naive, Divide-and-Conquer are all ways to solve algorithms. One such way is called dynamic programming (DP). In this article, we’ll take a look at what Dynamic Programming is, its characteristics, and the two main approaches to solving algorithms with DP.

## What Is Dynamic Programming?

The concept of dynamic programming was created to help improve the efficiency of brute-force or divide-and-conquer methods of solving algorithms.

Say, for instance, we have a knapsack and it can only fit a certain amount of items in it. What combination of items will give us the maximum value? Or, suppose we have a knapsack that has a certain weight capacity. What combination of items of given weights will give us maximum value? • Career Karma matches you with top tech bootcamps
• Access exclusive scholarships and prep courses

With dynamic programming, we take the problem and break it down into smaller overlapping sub problems. These problems are solved and stored in a data structure. More often than not, this type of approach will result in an optimal solution for the prompt your technical interviewer has given you. In the next few sections, we will take a look at three solution types: naive, top-down, and bottom-up.

## Naive Solutions

A naive solution is one that would be the first that comes to mind to a programmer. It may not be the most efficient, and it may not take advantage of some concepts. Yet, it is a simple solution that solves the problem. As a newer programmer, it is in your best interest to come up with naive solutions first and refactor to optimize it later.

## Top-Down Solutions

This is the first way to use dynamic programming in your solution. A top-down solution will take a naive solution that uses recursion and then add a technique called memoization to optimize it. Memoization acts like a sort of cache to store our sub-problems as we go so that the algorithm will run faster. Usually this occurs in the form of an object or a dictionary.

## Bottom-Up Solutions

Another type of dynamic programming solution that avoids recursion and tabulates from the beginning is called a bottom-up solution. This is a great way to go if you want to avoid using a lot of memory or prevent an accidental stack overflow.

Let’s take a look at two common problems in each of the approaches: Fibonacci and Longest Common Substring .

### Fibonacci

The Fibonacci Sequence is a series of numbers where each number is the sum of the previous two numbers, starting from 0 and 1:

```Fn = 0, 1, 1, 2, 3, 5, 8, 13, 21...etc.
0 + 1 = 1
1 + 1 = 2
1 + 2 = 3
2 + 3 = 5
3 + 5 = 8
5 + 8 = 13
8 + 13 = 21
13 + 21 = 34...etc.```

### The Prompt

Given a number, n , find the n th number in a Fibonacci sequence.

#### Solution 1: Naive

A naive solution is one that a programmer may come up with when first looking at a problem. Remember that naive doesn’t necessarily mean bad. A naive solution usually means the problem can be solved by using other methods that can create a more optimal or efficient solution. A naive solution is good because it means you are on the right track.

An example naive solution for Fibonacci looks like this:

```const fibNaive = (num) => {
if(num < 2) {
return num;
}

return fibNaive(num - 1) + fibNaive(num - 2);
};```

At the outset this looks fairly simple and straightforward. We are using recursion to solve this problem. Our base case returns the number if it is less than two. Otherwise, it uses recursion to get the ``` n th ``` number by adding each call to the stack until we hit the base case. Then it adds up all the calls together to get our result. Because we have two operations going ``` n ``` times, this is what we call O(2 n ) runtime. We measure how good a solution is by its Big O Notation . This is not an efficient solution because of its runtime, and should be avoided at all costs.

#### Solution 2: Dynamic Programming Approach #1 — Top-Down with Memoization

We can use the naive solution from above and add memoization to it to create a top-down solution to the problem. Memoization acts as a cache that stores the solutions to our sub-problems. Thus, we don’t have to calculate the Fibonacci sequence from the beginning every time. Here’s the code: "Career Karma entered my life when I needed it most and quickly helped me match with a bootcamp. Two months after graduating, I found my dream job that aligned with my values and goals in life!"

Venus, Software Engineer at Rockbot

```const fibMemo = (num, memo = { 0: 0, 1: 1 }) => {
if(num < 2) {
return memo[num];
}

let result = fibMemo(num - 1, memo) + fibMemo(num - 2, memo);
if(!memo[num]) {
memo[num] = result;
}

return result;

}```

The basic solution is the same here. But we’ve changed it up by adding a dictionary that will hold our Fibonacci values as we go through the recursion. Every time ``` n ``` changes, we’ll add a value to the ``` memo ``` object passed into the ``` fibMemo ``` function.

The base case is pretty much the same here. The difference is that we are starting with a default memo that has our first two Fibonacci numbers in it. This is instead of just returning the number passed in. We are assigning the variable result to our Fibonacci equation that we used in the return of the naive solution.

In the if statement , we are checking to see if the key exists in memo — if it doesn’t then we add it. We return the result just like we did in the naive solution.

Ultimately, there are two differences with this solution. For one, we added a ``` memo ``` object that remembers what we have figured out so far. And two, we added a conditional that checks to see if that key:value pair exists in the ``` memo ``` object. If not, it adds it.

This solution changes the time complexity from O(2 n ) to O(n) .

#### Solution 3: Dynamic Programming Approach #2 — Bottom-Up with Tabulation

This version of the solution uses iteration to solve the problem and tabulates the result as we go. We start with a JavaScript object (or an array is perfectly acceptable here too) that will store our values. We use those values to tabulate up to our ``` n th ``` number.

```const fibTab = (num) => {
let fibDict = { 1:0, 2:1 };

for(let i = 3; i <= num; i++) {
if(!fibDict[i]){
fibDict[i] = fibDict[i - 1] + fibDict[i - 2];
}
}
return fibDict[num];
}```

Just like the memoized version, this version is O(n) runtime because we iterate over every single number between ``` 1 `````` n ``` in this scenario.

Next, let’s take a look at another common problem, called the Longest Common Substring.

### Longest Common Substring

#### The Prompt

If given two strings, find the length of the longest common substring.

The longest common substring of ``` "ABABC" ``` and ``` "CABAB" ``` would be ``` "ABAB" ``` with a length of 4 because we see ``` "ABAB" ``` in both strings.

#### Solution 1: Naive Solution

A naive solution would be to find all the substrings in one string. Then, you would see if the other string has the substring, starting with the longest.

```const naiveSub = (str1, str2) => {
//find all the substrings.
substrs = [];
maxString = "";
otherString = "";
if(str1.length > str2.length) {
maxString = str1;
otherString = str2;
} else {
maxString = str2;
otherString = str1;
}

for(let i = 0; i < maxString.length - 1; i++) {
let str = "";
str += maxString[i];
for(let j = i + 1; j < maxString.length; j++) {
str += maxString[j];
substrs.push(str);
}
} // O(n) * O(n) === O(n^2)
//have all substrings
//see if other string has any of values from array in it.

let maxLength = 0;
let maxSubStr = "";

substrs.forEach(string => { // O(m)
if(new RegExp(string).test(otherString)) {
if(maxLength < string.length) {
maxLength = string.length;
maxSubStr = string;
}
}
});
return [ maxLength, maxSubStr ];
} // O(n^2 + m) <== Big O Notation for Naive Solution

console.log(naiveSub("ABABC", "CABAB"));```

The time complexity of the naive solution takes into account the size of both the substring array and the strings. The nested for loop is O(n 2 ) , and the forEach loop is O(m) . This is because the length of the array may be a different length than the strings. Since the two main blocks of code are stacked, we add the time complexities together. The final Big O is O(n 2 + m) . While a naive solution may not be the best solution, it works and will put you on track to find more efficient ones.

#### Solution 2: Top-Down Solution with Recursion

In dynamic programming, a top-down solution keeps track of the max count of letters in the substring each time we make a recursive call:

```const topDown = (str1, str2, count = 0) => {

let i = str1.length;
let j = str2.length;
//if the strings don't exist, return 0
if(i === 0 || j === 0) {
return count;
}

if(str1[i - 1] === str2[j - 1]) { // if the chars are the same, up the count and shorten string by 1
count = topDown(str1.slice(0, i - 1), str2.slice(0, j - 1), count + 1);
}
count = Math.max(count, //max between count and the other function
Math.max( // max between looking at shortening one word vs shortening the other word.
topDown(str1.slice(0,  i), str2.slice(0, j - 1), 0),
topDown(str1.slice(0, i - 1), str2.slice(0, j), 0)));

return count;
}

Time complexity for this solution is O(n + m) to account for the sizes of the different strings.

#### Solution 3: Bottom-Up Solution with Tabulation

The third solution to this problem involves using the bottom-up approach. In this approach, you would create a 2-D array/matrix that will tabulate what the max length of the substring is. The first thing to do is to create an empty matrix using the lengths of the strings.

```const create2DArray = (A, B) => {
const table = [];

for (let i = 0; i <= A.length; i += 1) {
table.push([]);
for (let j = 0; j <= B.length; j += 1) {
table[i].push(0);
}
}
return table;
};```

If our strings are ``` "techcareer" ``` and ``` "tech career" ``` our empty table will look like:

```[
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
]```

The purpose of creating an empty matrix is to create space in memory to tabulate and keep track of our matching substring lengths. As we go through we’ll keep track of the max value, so we can return it at the end of the function.

```const bottomUp = (A, B) => {
let table = create2DArray(A, B); // create the table
let max = 0; // initialize and declare max substring length to be 0
//start i and j at 1 so we can compare characters to previous row and column
for (let i = 1; i < A.length + 1; i += 1) {
for (let j = 1; j < B.length + 1; j += 1) {
//our initial row and column is set to 0
if (i === 0 || j === 0) {
table[i][j] = 0;
}
//if our strings chars are the same in the prev place
else if (A[i - 1] === B[j - 1]) {
//assign this spot in table to the table[i - 1][j - 1]'s value + 1
table[i][j] = table[i - 1][j - 1] + 1;
max = Math.max(max, table[i][j]); //compare the max to the new value at table[i][j] and reassign to max
} else {
table[i][j] = 0; //if the chars are not the same, it will reset count to 0. We still keep track of the max seen so far.
}
}
}
return max;
};
let str1 = 'techcareer';
let str2 = 'tech career';
console.log(bottomUp(str1, str2));```

The time complexity of this solution is not the best, at O(n * m) , where n and m consist of the different string sizes. Space complexity is O(n * m) , as well.

## Conclusion

In this article, we defined Dynamic Programming and how we can use it to make our naive solutions to problems more efficient. Don’t worry if Dynamic Programming doesn’t immediately come to you the first time you attempt it. Practicing this approach will help you get to the next level when it comes to data structures and algorithms!

About us: Career Karma is a platform designed to help job seekers find, research, and connect with job training programs to advance their careers. Learn about the CK publication.

## Christina Kopecky

About the author: Christina is an experienced technical writer, covering topics as diverse as Java, SQL, Python, and web development. She earned her Master of Music in flute performance from the University of Kansas and a bachelor's degree in music with minors in French and mass communication from Southeast Missouri State. Prior to joining the Career Karma team in June 2020, Christina was a teaching assistant, team lead, and section lead at Lambda School, where she led student groups, performed code and project reviews, and debugged problems for students. Christina's technical content is featured frequently in publications like Codecademy, Repl.it, and Educative.