Introduction to Dynamic Programming
Explore dynamic programming by understanding how to solve optimization problems through techniques like memoization and tabulation. Learn to identify overlapping subproblems and optimal substructure, and apply these methods to real-world problems such as palindrome checking, Fibonacci computation, route planning, and text justification.
We'll cover the following...
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 nth Fibonacci number. Let’s review the definition of the Fibonacci series:
...