Dynamic Programming: Introduction

Let’s go over the Dynamic Programming pattern, its real-world applications, and some problems we can solve with it.

Overview

Many computational problems are solved using a divide-and-conquer approach recursively. In these problems, we see an optimal substructure, i.e., the solution to a smaller problem helps us solve the bigger one. For example, is the string “rotator” a palindrome? We can start by observing that the first and the last characters match, so the string might be a palindrome. We shave off these two characters and try to answer the same question for the smaller string “otato”. We keep doing this until we are able to say a definite yes or no.

In some of the problems that can be solved with the above approach, there are many overlapping sub-problems. That is, we find ourselves solving the same sub-problem over and over. The recursive solution to the palindrome problem does not have this characteristic, but solutions to many other problems do have overlapping sub-problems. An example is the recursive computation of the nth Fibonacci number. Here’s the recursion tree for the solution to this problem with n = 4.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.