🎨 The ART of Dynamic Programming

An Intuitive Approach: From Apprentice to Master

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. 👍

Prerequisites

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.

-Mr. Rogers

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.

-Martin Luther King Jr.

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.

What is Dynamic Programming?

We will never know our full potential unless we push ourselves to find it.

-Travis Rice

There are two key ingredients to problems which can be solved by a Dynamic Programming algorithm:

What is the ART of Dynamic Programming?

Don't only practice your art, but force your way into its secrets. For it and knowledge can raise men to the divine.

-Ludwig van Beethoven

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 numbers? 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.

Step 1: All

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.

Step 2: Remember

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 available, 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 possibilities 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.

Step 3: Turn

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.

Step 4: Optional Memory Optimization

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(N²) 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.

Summary: The ART of Dynamic Programming

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

Visualization

Seeing is believing.

-Far Seer (Warcraft III)

Below is an oversimplified example which demonstrates the top-down solution's path (highlighted in yellow and green) and the bottom-up solution's path (highlighted in green).

We can "see" the downward staircase of recursive calls highlighted in yellow and the corresponding optimal solutions formulated in reverse as the recursive stack unwinds back up the staircase highlighted in green.

Each i^th mental leap of faith from i = 0..N-1 is highlighted in yellow as the recursive function go() invokes itself as a subroutine until the base case N = 4 is reached, ie. we recursively go() from here to there over and over again. As the recursive stack unwinds (highlighted in green), i^th sub-problem solutions are optimally built upon themselves. And we arrive at the same answer at the End.

The bottom-up solution has two key advantages over the top-down solution:

No recursive stack overhead
Memory optimization

It's worth noting that we can perform linear scans from the top-down solutions from i=0..N-1 or in the reverse direction from i=N-1..0, and likewise we can do the same for the bottom-up solutions. However, since the bottom-up solutions require explicit base cases to be defined to be iteratively built upon, it often makes sense to follow the recursive stack unwinding starting at N-1 because we can explicitly add base case(s) by appending them onto index N,N+1,N+2... to be iteratively built upon. See 712. Minimum ASCII Delete Sum for Two Strings as an example of bottom-up solutions performing linear scans in the opposite and same direction as the recursive stack unwinding, ie. starting from the top-left with empty string base cases at index 0 thus offsetting the dp matrix by 1 compared to starting from the bottom-right with empty string base cases at index M,N thus not needing to offset the dp matrix, simplifying the code.

Canonical Examples

It seemed unthinkable for me to leave the world forever before I had produced all that I felt called upon to produce.

-Ludwig van Beethoven

Emoji Legend 🧭

🛑 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 i^th item
🚫 Without
- "disclude this item" concept used for 0-1 knapsack algorithms where we find the optimal solution by either including xor discluding each i^th item
❌ Exit Conditions
- We can exit early under non-optimal conditions (ie. depth-first-search pruning) or for invalid inputs (ie. out-of-bounds)

N-Dimensional Top-Down + Bottom-Up:

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)

Kadane's Algorithm: Best Ending Here

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.

Recurrence Relation to Reduce Asymptotic Bounds via Pre-calculations:

Bottom-Up Sequentially Building Upon "K-th Buckets" of Previous Solutions:

Subproblems and Recurrence Relations

You have only begun to discover your power.

-Darth Vader

The most difficult part of dynamic programming is acquiring an understanding of a problem's subproblems and recurrence relations. It's amazing how difficult it can be to formulate DP solutions de novo with foresight conjured upon demand compared to validating existing DP solutions in hindsight. To develop a DP solution from scratch requires the creation of historical state variables and a series of states from which we consider all possibilities we can optimally choose from via recurrence relations which optimally build current subproblem solutions upon previous optimal subproblem solutions, ie. it is easier said than done.

krnets/The-ART-of-Dynamic-Programming