When I left you, I was but the learner, now I am the master.
Let us explore the intuitions of dynamic programming and transform our thoughts from "what the hell?" to "oh yeah, duh!" via a 3-step heuristic process. In hindsight, we can "see" the ART of dynamic programming is as easy as 1, 2, 3. 👍
You rarely have time for everything you want in this life, so you need to make choices. And hopefully your choices can come from a deep sense of who you are.
A significant amount of time and mental resources are necessary to begin understanding dynamic programming. Thus, DP is best approached as a "marathon", not a "sprint". Two key building blocks towards a basic understanding of DP are recursion and mathematical induction.
Note: When I mention "recursive stack unwinding" below, what I mean is "frames popping off the recursive call stack". And I imagine a similarity between this action and stepping down the stairs one-by-one, followed by stepping back up the stairs one-by-one in reverse. Stepping down the stairs would be equivalent to the recursive function being invoked as a subroutine of itself. And stepping back up the stairs would be equivalent to the recursive function invocations exiting their subroutines as the base case(s) are reached.
Take the first step in faith. You don't have to see the whole staircase, just take the first step.
A mental leap of faith is necessary to begin post-processing recursion and mathematical induction, ie. we can only understand the basic principles of recursion and recursive algorithms after we have assumed the inductive hypothesis of a recurrence relation is true. After taking this mental leap of faith, we can look back in hindsight with the mind's eye to discover what that actually means, ie. we can clearly "see" the recursive stack hit the base case(s) and begin to unwind, formulating an optimal solution built upon the optimal solutions to subproblems of the original problem itself.
We will never know our full potential unless we push ourselves to find it.
There are two key ingredients to problems which can be solved by a Dynamic Programming algorithm:
Don't only practice your art, but force your way into its secrets. For it and knowledge can raise men to the divine.
ART is an acronym used to intuitively create solutions to DP problems in 3 steps:
- All
- Remember
- Turn
These 3 steps are elaborated upon below, however, let us first take a minute to consider our end-goal, and how we can intuitively reach it. Our end-goal is to minimize or maximize an objective function within the given constraints of an arbitrary universe of discourse (ie. the problem statement).
Ask yourself this question: Is it possible to know the minimum or maximum objective function outcome without considering all possibilities? For example, let's say we have 3 numbers, and we want to know what is the minimum or maximum of those 3 numbers. Is it possible to know the minimum or maximum value without considering all of the card values? Please take a moment to consider this question before proceeding.
See Answer
The answer is obviously "no." It is not possible to know which of the 3 numbers are minimal or maximal unless we consider all 3 values. Using 3 cards as an example, let's assume we only know the values for the first two cards. Since we have not seen the third card's value, we don't know if it's less-than, equal-to, or greater-than the first two cards, and thus we cannot determine the objective function outcome without considering all of the card values.
All possibilities of a universe of discourse under consideration need to be checked before we can determine the objective function outcome. This realization allows us to begin creating a DP solution via a naive brute-force algorithm ie. an exhaustive search of all possibilities. Therefore, we begin by exploring all possibilites via top-down depth-first-search. Since we know we need to check all possibilities, this gives us key insight towards the N-dimensions of the corresponding DP memo which is used to remember the optimal solutions to each overlapping subproblem. This intuition leads us to step 2, but before we move on to step 2, let us first take another moment to consider the next key question.
Ask yourself this question: Is it possible to determine the objective function outcome without solving overlapping subproblems more than once?
See Answer
The answer is obviously "yes." With the properly structured N-dimensional memo we can store the optimal solutions to overlapping subproblems as they are computed, and then lookup previous solutions upon demand. This is the entire purpose of the DP memo. Simply remember each previous subproblem's optimal solution to avoid re-calculating it. In fact, this is raison d'être of dynamic programming, remembering the past to formulate the future, ie. use previous optimal subproblem solutions to formulate current optimal subproblem solutions to formulate the overall optimal solution for the original problem itself.
Remember each previous subproblem's optimal solution to avoid recomputing it. Combined with the previous "top-down brute-force" solution from step 1, we create the "top-down with memo" solution by simply using a memo to store and lookup solutions to previously solved subproblems. Thus a simple if-statement is added to the top of the recursive function to check if a solution to the subproblem is available. If the solution is availble, then return it immediately. If the solution is not available, then compute and store the solution once, thus making the solution available for future lookups. The memo is shaped as an arbitrary N-dimensional data structure such that each N-th dimension corresponds to a specific variable of the universe of discourse. Thus, the size of the N-dimensional data structure directly corresponds to the product of the coalesced variables of all possibilites under consideration. And it follows that the keys which uniquely identify each subproblem solution's storage position within the DP memo are all valid permutations of those specific variables per the constraints of the problem statement. The base case(s) of the recurrence relation are added to the memo first. And as the recursive stack unwinds, the base case(s) are iteratively and optimally built upon. This iterative building upon previous subproblem's optimal solutions from the bottom-up leads us to step 3.
Turn the "top-down with memo" solution upside-down to formulate an explicit bottom-up solution. This step can be challenging because the bases case(s) must first be explicitly specified before being iteratively built upon. The previous top-down solutions allow for the base case(s) to be implied by the recursion towards the base case(s) and thus implicitly stored by the memo as each recursive stack "bottoms out" (ie. hits the base case(s) and begins to unwind). To prepare for this implicit to explicit transformation, it can be helpful to print the key and value each time a subproblem's optimal solution is stored in the memo from the "top-down with memo" solution to explicitly identify the bases case(s) and to clearly understand how the recursive stack unwinds and thus dictates the iterative building upon the bottom-up recurrence relation. It can also be helpful to print the entire memo when the memo's dimensions can be easily visualized, ie. within 1- or 2-dimensions.
It may be possible to further reduce the bottom-up solution's memory consumption. For example, if we have a 2D matrix for the DP memo, but the current row is only dependent upon the previous row, then we can reduce memory from O(N2) to O(N) by replacing "dp[i]" with "cur" (ie. current row) and "dp[i - 1]" with "pre" (ie. previous row). Furthermore, if "cur" is only dependent upon itself, then we can also remove "pre". See 322. Coin Change and 518. Coin Change 2 as examples of this supplemental memory optimization which reduces the memory by a constant factor of N, ie. we only need N memory instead of 2 * N memory.
Computer, install a recursive algorithm.
-Ensign Harry Kim, Star Trek Voyager, Episode 102
The ART of DP in 3 steps:
- All possibilities are considered via top-down brute-force depth-first-search
- Remember each subproblem's optimal solution via a DP memo
- Turn the top-down solution upside-down to create the bottom-up solution
It seemed unthinkable for me to leave the world forever before I had produced all that I felt called upon to produce.
- 🛑 Base Case(s)
- Where the recursive stack "bottoms out" and begins to unwind
- 🎯 Recurrence Relation Target
- Determine the overall objective function outcome by recursively solving subproblems optimally
- 🤔 Memo
- Store and retrieve optimal solutions to previously solved subproblems within the N-dimensional memo data structure
- 👀 Seen
- Track which unique keys of the N-dimensional memo data structure have been previously seen
- ✅ With
- "include this item" concept used for 0-1 knapsack algorithms where we find the optimal solution by either including xor discluding each
ith item
- "include this item" concept used for 0-1 knapsack algorithms where we find the optimal solution by either including xor discluding each
- 🚫 Without
- "disclude this item" concept used for 0-1 knapsack algorithms where we find the optimal solution by either including xor discluding each
ith item
- "disclude this item" concept used for 0-1 knapsack algorithms where we find the optimal solution by either including xor discluding each
- ❌ Exit Conditions
- We can exit early under non-optimal conditions (ie. depth-first-search pruning) or for invalid inputs (ie. out-of-bounds)
It is our conviction, based on considerable experience teaching the subject, that the art of formulating and solving problems using dynamic programming can be learned only through active participation by the student. No amount of passive listening to lectures or of reading text material prepares the student to formulate and solve novel problems. The student must first discover, by experience, that proper formulation is not quite as trivial as on his own, he will acquire the feel for the subject that ultimately renders proper formulation easy and natural. For this reason, this book contains a large number of instructional problems, carefully chosen to allow the student to acquire the art that we seek to convey. The student must do these problems on his own. Solutions are given in the back of the book because the reader needs feedback on the correctness of his procedures in order to learn, but any student who reads the solution before seriously attempting the problem does so at this own peril. He will almost certainly regret this passivity when faced with an examination or when confronted with real-world problems. We have seen countless students who have clearly understood and can religiously repeat our lectures on the dynamic programming solution of specific problems fail utterly on midterm examinations asking that the same techniques and ideas be used on similar, but different, problems. Surprised, and humbled, by this experience, the same students often then begin to take seriously our admonition to do homework problems and do not just read the solution and think “of course that is how to do them,” and many have written perfect final exams. Why dynamic programming is more art than science we do not know. We suspect that part of the problem is that students do not expect to be called upon to use common sense in advanced mathematical courses and, furthermore, have very little practice or experience with common sense in this context. But common sense, not mathematical manipulation, is what it takes to be successful in a course in dynamic programming.
-The Art and Theory of Dynamic Programming Dreyfus and Law (1977)
- 5. Longest Palindromic Substring
- 45. Jump Game II
- 55. Jump Game
- 62. Unique Paths
- 63. Unique Paths II
- 70. Climbing Stairs
- 72. Edit Distance
- 91. Decode Ways
- 96. Unique Binary Search Trees
- 97. Interleaving String
- 120. Triangle
- 139. Word Break
- 140. Word Break II
- 198. House Robber
- 213. House Robber II
- 221. Maximal Square
- 256. Paint House
- 265. Paint House II
- 279. Perfect Squares
- 300. Longest Increasing Subsequence
- 322. Coin Change
- 337. House Robber III
- 354. Russian Doll Envelopes
- 416. Partition Equal Subset Sum
- 514. Freedom Trail
- 518. Coin Change 2
- 647. Palindromic Substrings
- 673. Number of Longest Increasing Subsequence
- 718. Maximum Length of Repeated Subarray
- 746. Min Cost Climbing Stairs
- 787. Cheapest Flights Within K Stops
- 799. Champagne Tower
- 877. Stone Game
- 983. Minimum Cost For Tickets
- 1025. Divisor Game
- 1035. Uncrossed Lines
- 1137. N-th Tribonacci Number
- 1140. Stone Game II
- 1143. Longest Common Subsequence
- 1235. Maximum Profit in Job Scheduling
- 1406. Stone Game III
- 1458. Max Dot Product of Two Subsequences
- 1463. Cherry Pickup II
- 1473. Paint House III
- 1510. Stone Game IV
- 1690. Stone Game VII
- 1696. Jump Game VI
- 1871. Jump Game VII
- 1879. Minimum XOR Sum of Two Arrays
- 1884. Egg Drop With 2 Eggs and N Floors
- 2008. Maximum Earnings From Taxi
We can perform a linear scan tracking the optimal solution ending at a specific index via a dynamic programming technique similar to Kadane's Algorithm.
- 42. Trapping Rain Water
- 304. Range Sum Query 2D - Immutable
- 307. Range Sum Query - Mutable
- 764. Largest Plus Sign
- 1139. Largest 1-Bordered Square
- 1895. Largest Magic Square
- 1991. Find the Middle Index in Array
- The ART of Dynamic Programming
- Competitive Programmer's Core Skills by Saint Petersburg State University
- Algorithms by Standford University
- Algorithms and Data Structures by UC San Diego
- Algorithms for DNA Sequencing
- Master Theorem: Determine the asymptotic bound of recursive algorithms via standard recurrences
- Towers of Hanoi
- Mathematics for Computer Science
- Algorithms: Dasgupta-Papadimitriou-Vazirani ( 2006 )
- Algorithms and Data Structures: Mehlhorn-Sanders ( 2007 )
- Introduction to Algorithms: Cormen-Leiserson-Rivest-Stein ( 2009 )
- Discrete Probability
- Mathematical Proofs
A major part of the art of dynamic programming is the appropriate choice of the subproblems that must be solved in order eventually to solve the given problem.
-The Art and Theory of Dynamic Programming Dreyfus and Law (1977)