Dynamic programming is not black magic

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.

[0] https://en.wikipedia.org/wiki/Dynamic_programming#History

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.

“Optimization” is similarly misleading (as someone who once took a CS class on “optimization” expecting something very different ;)).

Compare also 'Linear Programming'. Or the usage of a 'TV programme' or a 'musical programme'.

You forgot to define u and t.

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.

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.

This is the correct definition of dp.

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.

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.

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

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)

Agree. When I first learned the subject, my first thought was:

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.

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.

I remember learning about the knapsack problem and trying out recursive ways to solve it as well.

https://github.com/dsego/codility/blob/main/knapsack.js

There are dynamic programming solutions not based on memoization. See for example finding the longest common substring between two strings. Memoization will not help as much because you only need the table's left and up cells once.

In general, if the problem's sub-problems have a lot of overlap and the optimal subproblem must be part of the optimal overall solution, you've got an opportunity for dynamic programming. Saying memoization is the only kind of dynamic programming is like saying hash tables are the only abstract data type.

Memoization is a more general technique. It's often little more than caching the results you happened to compute, in case you need them again in the future.

Dynamic programming is systematic memoization. You solve subproblems of increasing size, until you reach a solution to the full problem. "Inductive algorithm" would be kind of appropriate term, as the typical dynamic programming algorithm is effectively a proof by induction. Unfortunately that term already has other meanings.

To my approach to dynamic programming, memoization is step 2 of 3.

1- find a recursive algorithm

2- memoization

3- make it iterative / bottom-up

3b- if possible, optimize for space

Step 3 is the most characteristic part of dynamic programming, but if you stopped at step 2, it would still qualify, I think, but it would not be as efficient as it could be.

Another way to think of step 3 would be: memoization is about caching, is there a way to pre-fill the cache?

Yes it would be wrong in my book. First i think a obvious counter example of memoization can be used outside of dynamic programing. Otherwise you can do most dynamic programming algorithms with storing the results in a table, and searching the table afterwards for the best answer. Memoization is basically a strategy to speed up algorithms.

That's exactly how I teach dynamic programming. First solve it recursively, then add memoization (I call that top-down).

Then notice that recursion and memoization has some overhead, and construct the table from bottom-up, remove the recursive call, and voila, dynamic programming.

Did he study under Kang at UCLA?

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.

I have listed a few in the article. It's pretty common to see them in lectures and practical exercices.

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

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.

Dijkstra is definitely dynamic programming, no doubt about it, you are still computing a new state from neighbouring state nodes while ignoring substantial number of non-neighbouring states.

You just have to accept the more abstract definition of "state" where the state encodes subsets of the graph. The states in Dijkstra are represented by subgraphs and distances that incrementally include more nodes leaving us with a path of states to follow in some order.

It's not much different from the traveling salesman or viterbi in that sense. You come up with some topological order of states in abstract state-space and then follow that topological order to compute the new state based on the adjacent previously computed states and never look back to update already finalised states.

With this more abstract point of view, it's clear Dijsktra is dynamic programming.

There is a whole field of graph dynamic programming problems. And the closely related Markov chain problems.

I totally agree in that I use the same mental model. But, if you look at it as “the shortest path must be the shortest path through one of its neighbors”, it can actually be classified as a dynamic programming algorithm!

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Dynamic...

Not quite, actually Dijkstra is a special case of what are called label correcting methods / algorithms (LCA) [1], which come directly from applying dynamic programming to the shortest path problem. LCA apply to all finite graphs with non-negative cycles and to be specific Dijkstra's algorithm is a LCA where in step one the node to be removed is choosen according to min_{i \in OPEN} d_i, see [1] for more.

[1]: https://web.mit.edu/dimitrib/www/DP_Slides.pdf (see lecture 3)

Do you mean tree rebalancing algorithms? I have to agree with this. AVL tree insertion is fine enough, but it gets hairy when you get to deletion. And Red-Black trees…

But how to you systematically deduce the tail recursion version?

I feel like, in this case, the recursivity in definition of Fibonacci and the recursivity in the tail recursion is just a coincidence, with the second just being a contrived way to write the loop you get after applying dynamic programming and trimming the table to only the last two elements.

Memoization generalizes much better than accumulator parameters.

I don't understand why you would use tail recursive functions for fibonacci ever and hence its relevance for dynamic programming. It can be solved with a simple equation with one input parameter. Solution left to OP as an exercise.

Because it's a good example to teach dynamic programming?

Thanks for the details. To add to this discussion, I have a script to see the progression over the days.

Looking at the last two columns, you can see how brutal 2023 was compared to 2022. Especially in the beginning. The first few days, most people keep playing, with a retention higher than 80% most days, and virtually everyone people solve both parts. In contrast, only 76% of people solved part 2 after solving part 1. And many people gave up on days 3 and 5.

Interestingly, the last few days are not that much lower. And that can be explained by the fact that AoC 2023 is more recent than AoC 2022, like you said. My interpretation is that this group of people will get over all the challenges regardless of the difficulty (to an extent, of course), while many other people will give up when they realize it will take too much of their time.

    Stats for year 2022 of Advent of Code
    -------------------------------------
    
    Day   Both puzzles   One puzzle       Total   Rel. puzzle 1/2   Rel. day before
      1        280,838       15,047     295,885              95 %             100 %
      2        232,752       12,403     245,155              95 %              83 %
      3        200,016       11,392     211,408              95 %              86 %
      4        184,435        3,734     188,169              98 %              92 %
      5        157,392        3,116     160,508              98 %              85 %
      6        155,921        1,602     157,523              99 %              99 %
      7        113,241        2,592     115,833              98 %              73 %
      8        107,224        7,659     114,883              93 %              95 %
      9         82,414       11,449      93,863              88 %              77 %
     10         85,075        5,511      90,586              94 %             103 %
     11         68,838        9,258      78,096              88 %              81 %
     12         59,253        1,061      60,314              98 %              86 %
     13         51,512        1,220      52,732              98 %              87 %
     14         49,051          991      50,042              98 %              95 %
     15         39,677        5,773      45,450              87 %              81 %
     16         23,298        5,650      28,948              80 %              59 %
     17         21,525        6,237      27,762              78 %              92 %
     18         25,420        4,927      30,347              84 %             118 %
     19         17,516          928      18,444              95 %              69 %
     20         22,141        1,003      23,144              96 %             126 %
     21         23,022        3,060      26,082              88 %             104 %
     22         15,393        5,083      20,476              75 %              67 %
     23         18,531          254      18,785              99 %             120 %
     24         16,419          252      16,671              98 %              89 %
     25         13,192        7,473      20,665              64 %              80 %
    ~/src/advent-of-code% ./stats.py 2023
    Stats for year 2023 of Advent of Code
    -------------------------------------
    
    Day   Both puzzles   One puzzle       Total   Rel. puzzle 1/2   Rel. day before
      1        230,737       73,941     304,678              76 %             100 %
      2        196,352        9,256     205,608              95 %              85 %
      3        130,406       19,913     150,319              87 %              66 %
      4        130,271       17,691     147,962              88 %             100 %
      5         80,255       31,029     111,284              72 %              62 %
      6        103,358        1,918     105,276              98 %             129 %
      7         81,905        7,308      89,213              92 %              79 %
      8         74,034       14,707      88,741              83 %              90 %
      9         76,438        1,229      77,667              98 %             103 %
     10         48,313       17,054      65,367              74 %              63 %
     11         57,339        2,386      59,725              96 %             119 %
     12         30,985       14,440      45,425              68 %              54 %
     13         38,217        5,223      43,440              88 %             123 %
     14         36,500        7,457      43,957              83 %              96 %
     15         40,881        4,156      45,037              91 %             112 %
     16         35,347        1,023      36,370              97 %              86 %
     17         24,014        1,097      25,111              96 %              68 %
     18         24,799        4,937      29,736              83 %             103 %
     19         22,525        7,197      29,722              76 %              91 %
     20         18,287        4,398      22,685              81 %              81 %
     21         14,311       10,149      24,460              59 %              78 %
     22         15,830          988      16,818              94 %             111 %
     23         14,562        2,964      17,526              83 %              92 %
     24         11,864        4,918      16,782              71 %              81 %
     25         10,522        3,048      13,570              78 %              89 %

This was just my personal experience (which certainly came from trying out a different language than I typically use in my day to day), but I'd argue that day 1 part 2 wasn't _hard_, but improperly specified from the prompt. The examples given are:

  two1nine
  eightwothree
  abcone2threexyz
  xtwone3four
  4nineeightseven2
  zoneight234
  7pqrstsixteen

  oneight

I didn't get very far into AoC this year as I ran out of time. Maybe I'll pick it up again later.

But my point is, I was surprised at how hard day 5, part 2 was. I didn't give up and solved it, but went away wondering whey I'd missed something obvious and overcomplicated it. So it brings some relief to know it was 'supposed" to be a bit challenging!

Early AoC was fun, you could get away without anything fancy until late in the game. Then it got harder, not fun, so I gave up and stopped touching it.

Genetic algorithms are not deterministic, whereas a DP solution is going to be deterministic with very easily calculable bounds on execution time. Comparing the two as you do, in my opinion, shows a fundamental gap in algorithms understanding.

Did you encounter practical problems where genetic algorithms work well? So far, the only serious usage I did was for CodinGame's Mars Lander optimization problem (and it works pretty well there!).

Do people use it much in their jobs?

I can't remember ever actually using it other than for puzzle-solving (like the excellent Advent of Code problems). I guess it's pretty common to use leet-code type problems for interviews, which maybe counts, but even there hopefully most employers aren't clueless enough to give people DP problems.

I've done some stuff around generating puzzles/levels/challenges for games that maybe could have used it, but it seemed like problems it might be useful for never came up for me... maybe because I found that you get better, funner puzzles and can control the difficulty better if the generator sort of "thinks like" a human solver/player would.

No doubt there are some edge cases, but how much are people really using DP at a job?

Effective web caching is black magic.

Thanks! I should have planned better for that before posting.

Interesting, I have never really looked into this kind of calculation. Thanks for the links!

The No True Scots Straw Man?

In general, it has great mechanical sympathy. You need to split your larger problem into smaller sub-problems, and then figure out which sub-problems depend on each other using the recursive formulation. Once you have done that, there should be no more need to have a stack, so you can just use an array to store the results of the depended on problems, and a loop to change which problem is being solved.

This article doesn't make the final step from recursion to loop but you would probably want to if you were doing DP in production.

Edit: Actually the article does make this jump. See the last code snippet before the conclusions section. Note also the second note after the snippet, which explains that the snippet itself uses a larger array than is necessary.

I understand! I do not think there is a magic formula for this. This only comes with a lot of practice.

I would argue that these are some of the most important algorithms in bioinformatics/biology. They have a wide range of applications.

That's a very good question.

I think the simplest approach to prove it would be to show that both computations yield the global minimum. Since there is only one global minimum, then they must be equal.

Amusingly, merit’s other meaning is the verb “to be worthy.”

Consider https://www.amazon.com/Dynamic-Programming-Coding-Interviews... for the most pedagogical approach I have seen.

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.