Hacker News Reader

Comment by gsf_emergency_2 | Hacker News Reader

It seems dynamic programming (some predetermined sequence of steps) as envisioned by Bellman is strictly less dynamic than ordinary programming today, hence the confusion?

Elevating "memoization+recursion" to "dynamic programming" seems like a development that Bellman didn't anticipate

https://cs.stackexchange.com/questions/99513/dynamic-program...

There is another mid century term which is oddly specific for something oddly general (or the other way?) "Operations Research"

Guess Bellman should have called it "Reactive Optimization", then we would have the totally appropriate "Recursive Memoization" or "Memoized Recursion"

View on HN

You should think of the “programming” in dynamic programming the same way you think of in linear programming, integer programming, and constraint programming.

Indeed even in layman’s terms, thinking of it as in television programming is more accurate than thinking it is related to computer programming (as is mentioned in TFA)

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

There was a universe before digital computers were popular or a thing at all.

Computing predates computers.

Before digital computers existed, there were still computers. They were people. A baker is a person who bakes. A computer was a person who computes (computing mathematical results).

Sure, that's why I had computers italicized to indicate the specific modern definition, not everything that computes.

In the UK at A-level (age 16-18) you may still be taught linear and dynamic programming before ever touching a line of code! (Indeed, that was the same for me!)

Did your school used the specific terms "linear programming" and "dynamic programming" to refer to those topics? My original comment didn't phrase this clearly, but I was thinking less about techniques themselves, and more about encountering them under those specific labels.

As an analogy, it's not unusual to learn a good chunk of calculus before learning that "calculus" is a thing they're part of - for example, by having an over-eager physics teacher who teaches you some of it so we can understand physics material deeper, but without ever mentioning the branch of math we're now using.

I know two people who are experts in linear programming who have never written a single line of code.

I meant that in particular you should _not_ think of the “programming” part of “dynamic programming” in the sense of computer programming

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

Television programming isn't a separate meaning from computer programming. Programming means creating a program. The program, whether you're talking about a computer, a television channel, or a live staged performance, is a list of what's going to happen in what order.

That's what I was hinting to. Pre mechanical programs were 'prewritten' sequences. Mostly linear, like a (literature) script. Musical score would fit that definition too. Then you can have slightly more complicated structures like dags and data flow, still linear in a way. When you add state,loops, feedback it gets interesting though.

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)

> Elevating "memoization+recursion" to "dynamic programming" seems like a development that Bellman didn't anticipate

Well, it also isn't a development that happened. You can (always) implement dynamic programming as recursion with memoization. But an algorithm that is recursive and memoized isn't necessarily an example of dynamic programming.

The point of dynamic programming is that you set up the recursion so that recursive calls do hit the cache, not that there is a cache and if you're lucky they might hit it.

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.

The sequence of steps is the result of dynamic programming. Not every sequence of steps is a dynamic programme. And (what I would argue are) the core results are fairly mathematical, memoization and recursion don't feature, but partial differential equations do. Check out the Hamilton Jacobi Bellman equation to get a flavour.

Reply on news.ycombinator.com