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?
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 nth 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 nth 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(2n) 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:
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(2n) 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 nth 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(n2), 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(n2 + 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:
"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 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;
}
console.log(topDown('alphabetical', 'abcada'));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.
