It's good that the article points out that DP algorithms are "just" clever ways to cache a recursion. Looking for a recursive solution is certainly the best way to start out looking for a DP solution, in my experience -- if you can find one, memoising it is trivial and may give a big speedup (and may even be faster than a "bottom-up" DP, since it only ever computes solutions that we definitely need).
With enough practice, it's usually possible to come up with a (correct but slow) recursive solution. When turning this into a DP, it doesn't matter if there are large numbers of subproblems in the call tree -- what's important is that there are a relatively small number of distinct subproblems. (Since there's no point caching a result that's only ever needed one time.) And that's where the difficulty tends to lie: Figuring out how to partition the original problem into few enough distinct subproblems.
> what's important is that there are a relatively small number of distinct subproblems.
This is the crucial part IMO. Whether the larger algorithm is recursive or iterative etc is secondary. But yes DP usually tends to show up in recursive algorithms most often.
> DP algorithms are "just" clever ways to cache a recursion
This is what made it click to me. When I was in university, perhaps because of the prevalence of procedural programming at the time
(as opposed to FP), DP looked magic to me with the bottom-up tabularization examples in the textbook.
Practically that is the way to do it because tail-call elimination isn't always applicable, but I wish they's taught us the more intuitive way to look at it first (top-down, cache a recursion)
The bottom-up tabularization isn't always necessary, but it's a key technique that is not just "avoiding overhead" or whatever. Doing the top-down memoization, you don't know which subproblems you need to store at any given, but going bottom-up, you do, and you can usually be much more clever about memory usage and overhead.
The obvious example is Fibonacci numbers: the "top down" memoized version needs to store every Fibonacci number in memory, because you don't know what number the recursion is asking for. But if you do it "bottom up", you know that to calculate f(N), you only need f(N-2) and f(N-1). Therefore, you only need to store the last two numbers, reducing your memory usage from O(n) to O(1).
This principle almost always applies in DP problems: for the "edit distance" problem, the number possible values for the function is N^2 (where N is the size of the two words you need to compare, assuming they're similar sizes), so the memoized version takes O(N^2) memory. But if you do it the "bottom up" version, you realize that to calculate all values in a row, you just need the previous row of values. So it takes memory from O(N^2) to O(N).
Point being: turning the recursion "upside down" is not just a thing you do to be clever (or to avoid "function calling overhead", something like that), it has very real algorithmic benefits, usually because it takes MUCH less memory to do it like that.
I'm sure you know this (since in my experience the history of the name is usually taught together with the technique), but for those reading along: the name "dynamic programming" originates from the late forties, early fifties. While the "office politics"-related motivation Richard Bellman gives for the name cannot be completely true due to anachronisms[0], it still fits with terms that made sense at the time, before the modern usage of "programming" existed:
> The word dynamic was chosen by Bellman to capture the time-varying aspect of the problems (...). The word programming referred to the use of the method to find an optimal program, in the sense of a military schedule for training or logistics. This usage is the same as that in the phrases linear programming and mathematical programming, a synonym for mathematical optimization.
I fully agree that would be nice if we relegated "dynamic programming" to a confusing historical umbrella term, and switched to less confusing names, like the ones you suggested. In that sense it is similar to "trie" - it's a funny pun, but incredibly impractical for verbal communication especially. It would be so much better if we all decided to just use "prefix tree" or "prefix search tree" and avoid the ambiguity.
This is a widespread misconception: thinking of dynamic programming as just a form of memoized recursion is not the way to learn DP because it makes it extremely difficult to understand how to do the style of DP problems that involve filling out a 2D array.
These are much more naturally done by filling out an array, right? I've never done them with a recursion; I can't say I've thought hard about it -- is there a natural recursive solution?
The point is that you don't have to exactly fill the 2D array to solve the problem in that way. The 2D array is an optimization in this view, and can be safely replaced with a cache without breaking the correctness. Of course there is also some learned techniques specific to dynamic programming, and that makes it worthy to learn at some point because otherwise you will never think of them, but at its core dynamic programming is just a specific way of doing recursion.
Not the best runtime (I could use a multidimensional array instead of an hash map for the cache, and recursion is "slow" in Python), but it's a clear solution.
Given a recursive solution, it is also "trivial" to convert it into filling an array by visiting the recursive states in reverse topological order. So here is a submission that fills in the array: https://leetcode.com/problems/best-time-to-buy-and-sell-stoc...
The issue I have with not connecting dynamic programming with caching is that it becomes an exercise in cleverness, and many people just give up. It was pretty fun in school, but if I need colleagues to ramp up on it, I need a more effective approach. Sure, they might not grok the full theory right away, but they won't use it at all, and definitely won't get to the theory, if they think it's too abstract for them.
The best analogy I have here is that saying "DP is just caching/memoization" is like saying "investment is just buying stuff and selling them later." Regardless of how technically accurate it might be, it misses such massive complexities and difficulties in the topic that it just makes you look silly rather than insightful.
Would you prefer someone start learning the principles of investing from an initial premise of “investment is just spending money to make money” or “investment is just buying something for less than it will be worth in the future”
Both are technically correct and both statements are vast oversimplifications of a complex subject, however the second statement leads into more advanced topics naturally, creating a smoother progression of knowledge that builds on itself.
Every complex topic generally starts with a few foundational bits of knowledge that support the whole house of cards. Pick the wrong foundational bits and you won’t get as far.
Origin of the name "dynamic programming", from its inventor, Richard Bellman:
"I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. An interesting question is, ‘Where did the name, dynamic programming, come from?’
The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence.
You can imagine how he felt, then, about the term, mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose?
In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word, ‘programming.’ I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying—I thought, let’s kill two birds with one stone. Let’s take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it’s impossible to use the word, dynamic, in a pejorative sense.
Try thinking of some combination that will possibly give it a pejorative meaning. It’s impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities”.
I really like how this article exposes the problem recursively first then progressively adds caching, and finally reduces the size of the cache to only what is necessary.
I have often made the mistake of trying to get to the dynamic programming solution directly, and either got stuck or had to go through heroic efforts to get it working. I think from now on, I will force myself to go through the steps in order.
From my own experience, being taught dynamic programming straight way makes it more of a puzzle. By going through the steps and explaining _why_ we are using a table, and connecting the concept to caching, I feel like it makes much more sense.
I had a very good algorithms professor. He studied at UCLA. His classes about dynamic programming were superb. He started with a problem for which the naive solution was simple and had exponential complexity. Then he broke the problem into smaller problems and reduced the complexity to something polynomial. Then he applied memoisation and the complexity dropped to linear.
I really would like to remember the problems he used.
1. *Fibonacci Sequence*: The classic example where the naive recursive solution has exponential complexity. By storing previously computed values (memoization), the complexity can be reduced to linear.
2. *Coin Change Problem*: Given different denominations of coins and a total amount, finding the number of ways to make the change. The naive approach is exponential, but dynamic programming reduces it to polynomial complexity.
3. *Knapsack Problem*: Particularly the 0/1 Knapsack problem, where items with given weights and values must be placed in a knapsack of a fixed capacity to maximize total value. The naive exponential solution can be optimized using dynamic programming.
4. *Matrix Chain Multiplication*: Determining the most efficient way to multiply a chain of matrices. The problem can be solved in exponential time using a naive approach but becomes much more efficient with dynamic programming.
5. *Longest Common Subsequence*: Finding the longest subsequence common to two sequences. A classic dynamic programming problem that can be solved in polynomial time.
6. *Longest Increasing Subsequence*: Finding the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
7. *Shortest Path Problems*: Like the Floyd-Warshall algorithm for finding the shortest paths in a weighted graph with positive or negative edge weights.
8. *Edit Distance (Levenshtein Distance)*: Finding the minimum number of edits (insertions, deletions, substitutions) needed to change one word into another.
9. Longest Path in DAGs: Find a longest path in a directed acyclic graph.
10. Weighted Independent Set on a Path: Given an array of integers, compute the maximum sum of numbers provided that you may not take two consecutive cells.
I am a big fan of the Knight Dialer. I wrote an article on it and how you can actually use graph theory to reduce it to an incredibly efficient 4x4 matrix. was super fun.
In addition to the suggested problems others posted, perhaps it was a scheduling problem? Like, for example, scheduling N overlapping events in time, like course schedules or processes for a CPU. Generally this would be done to optimize something like throughput - I believe that when you start adding special requirements, like "These 2 courses must be taken together", then things get much more complicated and intractable compared to plain-old dynamic programming.
Dynamic programming is what allowed me to compute the number of legal Go positions [1,2], a 171 digit number.
While the naive method would take time 3^n^2 to examine all possible positions on an nxn board, dynamic programming effectively strips away one dimension, reducing time to O(n^5 * 5.4^n), while using space O(n * 5.4^n).
The name "Dynamic Programming" might seem out of place because it doesn't come from programming as a discipline. In this case, it actually refers to something like optimization, similar to linear programming. Dynamic programming is basically a method you can use to solve decision problems with discrete time, i.e picking the optimal sequence {a_t} in order to maximize \sum_t u_t(a_t) (plus constraints). The "dynamic programming" is defining a value function V* where V*(t) = max_{a_t}{ u_t(a_t) + V*(t-1) } which greatly reduces the dimensionality of the optimization problem.
In fact, the official line [0] on where the name comes from is quite funny. I shall quote my favourite part:
> [Dynamic] also has a very interesting property as an adjective, and that is it's impossible to use the word dynamic in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It's impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to.
My dad told me a joke/story once about one of his old psychologist colleagues(call him Dave) arguing with a psychoanalyst* about some psychology thing.
After a while of the discussion going nowhere, the psychoanalyst said something like this. "Not to worry, Dave, I know you're dynamically minded enough that you'll eventually learn to agree with me."
Dave was not pleased.
I guess that was more condescending than pejorative, but oh well.
(Most modern clinical psychologists consider psychoanalysis to be a pseduoscience. A small minority still practice it even clinically. They don't like eachother very much)
Scripting languages are called 'dynamic' sometimes pejoratively. Dynamic microphones are also inferior in studio recording situations. I could see a poor DP implementation wasting memory being described negatively.
But I would still point out that this is the exact reason “dynamic” does not help if you do not know about the history. Since it can be applied to anything, it does not help you trim down what it can refer to.
Most of the time I hear the term being used by other people (not you :) ), I feel it's for showing off and look smarter than everybody else - "Look, I used dynamic programming to solve that problem", when in fact they were just employing what I'd consider the natural and intuitive approach for solving the problem. There was nothing they actually "used", besides happening to identify that the problem could be broken into progressively smaller subproblems.
It's interesting how computing things - like optimization problems - used to be much more dominant in terms of what people thought about and did with computers. It feels like most of the time we are just doing data storage and retrieval combined with networking... some computations are embedded within those things, but usually well encapsulated.
If you go further back, "programming" describes it precisely, and what we call "programming" today is "writing code" which can be subdivided into different kinds of "programming" such as functional, declarative, procedural, etc. But there's a lot more that fits under that umbrella.
Yeah the "programming" part has always thrown me off when I started my first Engineering job one of the guys was always talking about an "LP" model I thought it was some deep piece of black magic until I realized it was essentially brute searching for a solution to a series of simultaneous equations.
I think "Linear Optimization" might be a better term, or maybe "Linear Solving".
That’s the programming part. As others have shared, the “Dynamic” part was made up by Bellman so it sounded important and politicians wouldn’t try to cut his funding. It’s often applied to dynamical systems, but that’s a coincidence.
Readit News
With enough practice, it's usually possible to come up with a (correct but slow) recursive solution. When turning this into a DP, it doesn't matter if there are large numbers of subproblems in the call tree -- what's important is that there are a relatively small number of distinct subproblems. (Since there's no point caching a result that's only ever needed one time.) And that's where the difficulty tends to lie: Figuring out how to partition the original problem into few enough distinct subproblems.
This is the crucial part IMO. Whether the larger algorithm is recursive or iterative etc is secondary. But yes DP usually tends to show up in recursive algorithms most often.
This is what made it click to me. When I was in university, perhaps because of the prevalence of procedural programming at the time (as opposed to FP), DP looked magic to me with the bottom-up tabularization examples in the textbook.
Practically that is the way to do it because tail-call elimination isn't always applicable, but I wish they's taught us the more intuitive way to look at it first (top-down, cache a recursion)
The obvious example is Fibonacci numbers: the "top down" memoized version needs to store every Fibonacci number in memory, because you don't know what number the recursion is asking for. But if you do it "bottom up", you know that to calculate f(N), you only need f(N-2) and f(N-1). Therefore, you only need to store the last two numbers, reducing your memory usage from O(n) to O(1).
This principle almost always applies in DP problems: for the "edit distance" problem, the number possible values for the function is N^2 (where N is the size of the two words you need to compare, assuming they're similar sizes), so the memoized version takes O(N^2) memory. But if you do it the "bottom up" version, you realize that to calculate all values in a row, you just need the previous row of values. So it takes memory from O(N^2) to O(N).
Point being: turning the recursion "upside down" is not just a thing you do to be clever (or to avoid "function calling overhead", something like that), it has very real algorithmic benefits, usually because it takes MUCH less memory to do it like that.
As fancy as that feature is, it should be called array memoization, or call stack memoization.
The term "dynamic programming" should be reserved for something better. IMO.
> The word dynamic was chosen by Bellman to capture the time-varying aspect of the problems (...). The word programming referred to the use of the method to find an optimal program, in the sense of a military schedule for training or logistics. This usage is the same as that in the phrases linear programming and mathematical programming, a synonym for mathematical optimization.
I fully agree that would be nice if we relegated "dynamic programming" to a confusing historical umbrella term, and switched to less confusing names, like the ones you suggested. In that sense it is similar to "trie" - it's a funny pun, but incredibly impractical for verbal communication especially. It would be so much better if we all decided to just use "prefix tree" or "prefix search tree" and avoid the ambiguity.
[0] https://en.wikipedia.org/wiki/Dynamic_programming#History
For example, look at the "best time to buy and sell stock" series on leetcode: https://leetcode.com/problems/best-time-to-buy-and-sell-stoc....
These are much more naturally done by filling out an array, right? I've never done them with a recursion; I can't say I've thought hard about it -- is there a natural recursive solution?
(I linked to iii above but for anyone who hasn't tried them they are a great intro to DP problems; start with the first one: https://leetcode.com/problems/best-time-to-buy-and-sell-stoc...)
Not the best runtime (I could use a multidimensional array instead of an hash map for the cache, and recursion is "slow" in Python), but it's a clear solution.
Given a recursive solution, it is also "trivial" to convert it into filling an array by visiting the recursive states in reverse topological order. So here is a submission that fills in the array: https://leetcode.com/problems/best-time-to-buy-and-sell-stoc...
It does't work all the time like that since caching increases the Space Complexity.
There are DP problems that can be solved without storing all possible values in an array.
Deleted Comment
Both are technically correct and both statements are vast oversimplifications of a complex subject, however the second statement leads into more advanced topics naturally, creating a smoother progression of knowledge that builds on itself.
Every complex topic generally starts with a few foundational bits of knowledge that support the whole house of cards. Pick the wrong foundational bits and you won’t get as far.
https://github.com/dsego/codility/blob/main/knapsack.js
"I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. An interesting question is, ‘Where did the name, dynamic programming, come from?’
The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence.
You can imagine how he felt, then, about the term, mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose?
In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word, ‘programming.’ I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying—I thought, let’s kill two birds with one stone. Let’s take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it’s impossible to use the word, dynamic, in a pejorative sense.
Try thinking of some combination that will possibly give it a pejorative meaning. It’s impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities”.
Source:
https://alliance.seas.upenn.edu/~cis520/dynamic/2021/wiki/in...
I have often made the mistake of trying to get to the dynamic programming solution directly, and either got stuck or had to go through heroic efforts to get it working. I think from now on, I will force myself to go through the steps in order.
* https://en.wikipedia.org/wiki/Sequence_alignment
* https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algor...
* https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorit...
I really would like to remember the problems he used.
2. *Coin Change Problem*: Given different denominations of coins and a total amount, finding the number of ways to make the change. The naive approach is exponential, but dynamic programming reduces it to polynomial complexity.
3. *Knapsack Problem*: Particularly the 0/1 Knapsack problem, where items with given weights and values must be placed in a knapsack of a fixed capacity to maximize total value. The naive exponential solution can be optimized using dynamic programming.
4. *Matrix Chain Multiplication*: Determining the most efficient way to multiply a chain of matrices. The problem can be solved in exponential time using a naive approach but becomes much more efficient with dynamic programming.
5. *Longest Common Subsequence*: Finding the longest subsequence common to two sequences. A classic dynamic programming problem that can be solved in polynomial time.
6. *Longest Increasing Subsequence*: Finding the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
7. *Shortest Path Problems*: Like the Floyd-Warshall algorithm for finding the shortest paths in a weighted graph with positive or negative edge weights.
8. *Edit Distance (Levenshtein Distance)*: Finding the minimum number of edits (insertions, deletions, substitutions) needed to change one word into another.
9. Longest Path in DAGs: Find a longest path in a directed acyclic graph.
10. Weighted Independent Set on a Path: Given an array of integers, compute the maximum sum of numbers provided that you may not take two consecutive cells.
- longest common subsequence
- longest common substring
- line warp
- subset sum
- partition
- knapsack
You can also have a look at [1] for more ideas.
[1] https://en.wikipedia.org/wiki/Dynamic_programming#Algorithms...
Since it got the hug of death
While the naive method would take time 3^n^2 to examine all possible positions on an nxn board, dynamic programming effectively strips away one dimension, reducing time to O(n^5 * 5.4^n), while using space O(n * 5.4^n).
[1] https://tromp.github.io/go/legal.html
[2] https://tromp.github.io/go/gostate.pdf
> [Dynamic] also has a very interesting property as an adjective, and that is it's impossible to use the word dynamic in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It's impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to.
[0] https://en.wikipedia.org/wiki/Dynamic_programming#History
After a while of the discussion going nowhere, the psychoanalyst said something like this. "Not to worry, Dave, I know you're dynamically minded enough that you'll eventually learn to agree with me."
Dave was not pleased.
I guess that was more condescending than pejorative, but oh well.
(Most modern clinical psychologists consider psychoanalysis to be a pseduoscience. A small minority still practice it even clinically. They don't like eachother very much)
But I would still point out that this is the exact reason “dynamic” does not help if you do not know about the history. Since it can be applied to anything, it does not help you trim down what it can refer to.
Which is what dynamic programming is about. And no, not everyone is capable to do that, especially since not all problems solved at work are Leetcode.
Sometimes people really have to spend hours or days to understand how to split a problem. Only then optimizations can be applied or become "obvious".
Like usual, solutions are "so obvious" when someone has done a lot of heavy lifting to simplify the problem, improve the context, etc.
Dynamic programming is a whole chapter in most algorithms books. It's not about showing off, it's the name of the technique.
I think "Linear Optimization" might be a better term, or maybe "Linear Solving".