“Dynamic programming” is not referring to “computer programming”

Fun enough, in commercial software engineering your solution won’t raise eyebrows as something routine and expected, but an efficient algorithm could do.

Had a similar problem in a highschool comp. sci. class with a maze-following algorithm where you got points off for back-tracking. Turns out your code could pre-fetch the entire maze before making a move, which I think goes against the spirit of the exercise.

I think I know the culprit. The story I was told is that the person precomputed some of the results and submitted a huge source file (in tens of megabytes) of hard coded data. This probably led to subsequent amendment of the rules regarding source file sizes.

I'll report back once I find the persons involved.

No, sorry. I vaguely remember compile time limits, but they were high enough (30 seconds, I think?) that I didn't bother worrying about them (at least, that's my memory).

That sounds very smart :D

Marketing, Richard Bellman was trying to get funding and needed his work to sound high tech and fancy.

According to wikipedia: https://en.wikipedia.org/wiki/Dynamic_programming#History_of...

The word dynamic was chosen by Bellman to capture the time-varying aspect of the problems, and because it sounded impressive.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.

Also, Harold J. Kushner stated in a speech that, "On the other hand, when I asked [Bellman] the same question, he replied that he was trying to upstage Dantzig's linear programming by adding dynamic.

When I learned dynamic programming, I was told this was in contrast to simple memoization in that memoization is a cache of computation, dynamic programming involves a "choice" in each step.

For example let's look at the fibonacci sequence, F(n) = F(n-1) + F(n-2), naively you just fill in a (1 dimensional) table with the results [1, 1, 2, 3, 5, 8, 13...] and it feels static because there's nothing to choose or decide.

In contrast for example the longest common subsequence looks like this:

  lcs[m, n] = 0                 if m = 0 or n = 0
  lcs[m, n] = lcs[m-1, n-1] + 1  if X[m] = Y[n]
  lcs[m, n] = max(lcs[m-1, n], lcs[m, n-1])  if X[m] != Y[n]

I also discovered the term "dynamic programming" 20 years in my career, when doing leetcode training for a job interview.

I still have no idea why it's called "dynamic".

According the article, the term “dynamic” was chosen because it has positive connotations.

As others have mentioned the term was chosen to be distinctive and attractive.

The term always made me insufficient as I always assumed it meant much more and I just didn’t understand how.

In the Fibonacci example, it seems more like common sense to avoid recomputing expensive things. Instead we should give derogatory names to the inefficient implementations, not an opaque name to the only sane implementation.

Nice! I guess you must know Bruce Merry. Once, when practicing, I kept on hitting my head on a problem. On the spur of the moment, I decided to fire off an email to Bruce (given his track record, I was like "if anyone can figure this out, he can"). I was shocked (and very pleased) to get a reply a few days later outlining his thought process and how he went around solving the problem.

I used to know the ZA team leaders as well (after competing, I was a team leader for several more years).

To be fair, DP generally also involves recursion in some way. You could describe it as a lookup table where, to fill in later entries of the table, you need to use the earlier entries.

Yes, absolutely. I did programming competitions back in high-school (around 10 years ago) and common folklore was that back in the days knowing dynamic programming could win you a medal, but today it was just basic expected knowledge.

Dynamic programming is for me one of the things that really scratched an itch and made me start liking programming. The invariant/inductions of composing smaller things into a bigger solution is so elegant.

I do feel dynamic programming influences how I solve problems in my work. How, if you compose the problem correctly, it can never reach a fault state in a sense. Not sure if I'm able to explain what I mean, but for instance I recently refactored an old application at work that had lots of bugs, was hard to grasp and had loads of error checking code / asserts. However, by composing it a bit differently, modeling it properly, I could remove swaths of code / defensive programming because I with the help of the compilator now can guarantee the base cases holds etc.

Edit: one a bit contrived example might be an Order. If you have one big model tracking the lifetime of an order, some fields will have to be null until they have a value. For instance a field sent_at_time. Then you have a function that generates an email to the customers, which uses that field. How do you handle that field possibly being null? Do you say "I know that at this point in time, this field is always set since the email is generated after sending" and tell the compiler to ignore the possibly null value? Or do you handle the possible null with some error handling / fallback value, that in practice is dead and cluttered code and will just confuse a future developer seeing it with questions like "how can this happen"?

With the lessons from dynamic programming in mind, I think both are bad solutions. You want to be able to go from state n to n+1 with safety (order purchased, ordered sent, email sent). So model it in a way that the email sending code only ever can get an order in the correct previous state as input. Then if the assumption were to break in the future (maybe some orders are digital and the email is sent without the order having been physically sent), that breaking assumption will immediately be obvious in how the state/models are composed, and not in runtime when either the not-null-assert fails or the emails start having the fallback value.

I think of "programming" in "dynamic programming" the exact same way I think of it in "linear programming", "integer programming" and "constraint programming": it's probably some kind of software development that some computer scientists came up once and that I don't need to think about, because my normal programming has worked out pretty well so far

(Except, well, I guess I understand what "dynamic programming" is more than I understand what the other forms of programming you mention is; "dynamic programming" is solving certain classes of recursive problems by using arrays, sometimes nested arrays, to avoid re-computation, and somehow that's supposed to be more "dynamic" than not doing that)

> linear programming, integer programming, and constraint programming

Can't think of a universe in which you'd learn about these things before learning "computer programming".

I always find funny how many meanings "programming" has.

Usually though when using recursion to solve an algorithmic problem, people memoize results they know will be needed later again. So in most cases that should automatically become the same thing in practice.

> dynamic scoping

Right you are. Even more horrible. The tcl language still has it!

Isnt dynamic scoping a bit similar to Dependency Injection? Maybe there's a form of it that could be useful. Like explicit dynamic scopes?

Both meanings derive from Bellman. "Reinforcement learning" did not invent a new way, and the field of reinforcement learning predates leetcode by a large margin.