Dissecting Dynamic Programming — The Beginning
I find Dynamic Programming fascinating and intellectually challenging. The goal of this “Dissecting Dynamic Programming” series is to share the insights I gather while studying and solving this class of problem.
“The Best Way to Learn Something is to Teach it to Someone Else” is one of the well-known proverbial wisdom quotes. This blog series is intended for the following reasons:
- Record the insights I extract from solving Dynamic Programming problems
- For fellow Dynamic Programming enthusiasts to leverage the recorded insights to expedite their journey in mastering Dynamic Programming problems
To kick off this series, the below sections will describe the two important concepts in Dynamic Programming and then show the manifestation of those two concepts in a canonical example.
The following two concepts are extremely important to grasp and they will become very obvious after you have solved a handful of Dynamic Programming problems.
Concept #1: Optimal Substructure
The technical description of this concept is “a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems” — by Wikipedia
The central idea in solving Dynamic Programming problems is to first identify the sub-problems and their relation and then find the solution to those sub-problems. Finally use those sub-problem solutions to form the final solution.
The above description hopefully invokes an image of the subproblems tree.
Concept #2: Overlapping sub-problems
This concept is very important and easier to grasp. To be considered as a Dynamic Programming problem, it must exhibit this property. Among the many subproblems in the original problem, some of those are the same. Therefore it is more efficient to compute the solution to those same subproblems only once and reuse them when needed.
If those subproblems are solved a certain order (left to right, or right to left), then it is very easy to reuse the already stored solutions. Memoization is a technique to remember the solution to subproblems that was just computed.
This section will dissect a Dynamic Programming problem called Fibonacci sequence to illustrate the above 2 very important concepts.
Fibonacci sequence is a well-known sequence of numbers that looks something like this 0,1,1,2,3,5,8,13, 21,….. Please see Wikipedia for more details. The recurrence relation for Fibonacci sequence is:
fib(n) = fib(n-1) + fib(n-2) where fib(0) = 0 and fib(1) = 1
Let’s use a concrete Fibonacci sequence example fib(4). Based on the recurrence relation above, then fib(4) = fib(3) + fib(2). If somehow we have the solution to fib(3) and fib(2), then we can sum them up the come up with the solution to fib(4). By applying the same recurrence relation, we can further break fib(3) and fib(2) to smaller subproblems like in figure #1
The fib(4) tree in Figure #1 exhibits the “optimal substructure” property because the optimal solution of fib(4) comes from combining the optimal solution from its subproblems, namely f(3) and f(2).
Figure #1 also tells us fib(4) has 8 subproblems, and some of them are overlapping, meaning they appear more than once, f(2) and f(1). For a larger Fibonacci sequence like f(10), there would see a much larger number of overlapping subproblems.
To solve a Dynamic Programming problem, we would have to reason through the problem statement and work through a few examples in order to come up with the recurrence relation as well as a recursion tree to better understand the subproblems and to confirm whether they exhibit the “optimal substructure” and “overlapping subproblems” properties.
From the recurrence relation, then we can translate it to code to solve the problem using either the top down approach or bottom up approach. For some us, the transition is not very obvious and natural. I hope to share a few insights in future blogs to help the transition to be much smoother.
There is a plethora of resources for one to learn about the basics of solving Dynamic Programming problems. That is not the main intention of this blog series, rather I aim to share insights that one can leverage to gain a deeper understanding at solving simple to more complex Dynamic Programming problems.
For now, please bookmark the Leetcode Dynamic Programming problem list below. It will come in handy in the future.
In the next blog, I will share insights about translating a recurrence relation to the “top down” and “bottom up” solutions.
Blogs in This Series:
- Dissecting Dynamic Programming — Top Down & Bottom Up
- Dissecting Dynamic Programming — Recurrence Relation
Resources:
