Dynamic Programming: Introduction

About the pattern

Many computational problems are solved by recursively applying a divide-and-conquer approach. In some of these problems, we see an optimal substructure, i.e., the solution to a smaller problem helps us solve the bigger one.

Let’s consider the following problem as an 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”. The subproblems we encounter are: “rotator”, “otato”, “tat”, and “a”. For any subproblem, if the answer is no, we know that the overall string is not a palindrome. If the answer is yes for all of the subproblems, then we know that the overall string is indeed a palindrome.

While each subproblem in this recursive solution is distinct, there are many problems whose recursive solution involves solving some subproblems over and over again (overlapping subproblems). An example is the recursive computation of the n^th Fibonacci number. Let’s review the definition of the Fibonacci series: