6 ms·
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 l
by _v7gu 3y ago
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.
- glimshe 3y agoMost 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.
- valval 3y agoWell aren’t you cynical.
- mk89 3y ago> happening to identify that the problem could be broken into progressively smaller subproblems. 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.
- bcrosby95 3y agoDo you feel similarly if someone says they used an iterative, recursive, or greedy algorithm? Dynamic programming is a whole chapter in most algorithms books. It's not about showing off, it's the name of the technique.
- throwaway2037 3y agoAs I interpret the GP, the person is peacocking or gate-keeping by (humble)bragging about using dynamic programming to solve a problem. For all we know, they Googled for an efficient algorithm and copied the result. I have done it before, and I have no shame about it. If a teammate asks me how I knew about that dynamic programming algorithm, I would reply: "Are you joking? I could never program that myself. Thank you Google." Except for a few algorithms, most are solved using iterative or recursive.
- uoaei 3y agoIf 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.
- roenxi 3y agoIn 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 https://en.wikipedia.org/wiki/Dynamic_programming#History
- smokel 3y agoDynamic typing comes to mind ;)
- kevindamm 3y agoDynamic scoping ;)
- tempodox 3y agoYou cannot get any more pejorative. Mission accomplished!
- peterfirefly 3y agoDynamic ethics.
- mtlmtlmtlmtl 3y agoMy 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)
- asimpletune 3y agoThis is the correct definition of dp.
- eru 3y agoCompare also 'Linear Programming'. Or the usage of a 'TV programme' or a 'musical programme'.
- tnecniv 3y agoThat’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.
- bigger_cheese 3y agoYeah 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".
- eru 3y agoModern Linear Programming solvers are a lot more advanced than 'brute searching'. But otherwise, you are right.
- cubefox 3y agoYou forgot to define u and t.
- layer8 3y ago“Optimization” is similarly misleading (as someone who once took a CS class on “optimization” expecting something very different ;)).
- LudwigNagasena 3y agoOptimisation is just function minimisation/maximisation. What did you expect and how was it different?
- hcs 3y agoNot speaking for the GP but I'd imagine "optimizing" for performance. I had a professor who would get very irritated when anyone mentioned "optimizing" a program for just this reason, since you weren't finding the best possible runtime.
- LudwigNagasena 3y agoOh, makes sense, performance optimisation didn’t cross my mind for some reason.
- closeparen 3y agoIt'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.