7 ms·

"and candidates who haven't usually don't even have a chance at solving them" I am one of those candidates, and I don't know why it is called Dynamic programmi

• hhmc 8y ago
  The etymology comes from the field of mathermatical optimization, not from programming as commonly understood today.
• RJIb8RBYxzAMX9u 8y ago
  > [...] I don't know why it is called Dynamic programming. In this context "programming" means "optimization"[0]. [0] https://en.wikipedia.org/wiki/Mathematical_optimization https://en.wikipedia.org/wiki/Mathematical_optimization
• mafm 8y ago
  > [...] I don't know why it is called Dynamic programming. According to Richard Bellman, who came up with the name: 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. [...] 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" [...] 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.
  • jonsen 8y ago
    Formatted for mobile: According to Richard Bellman, who came up with the name: 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. [...] 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" [...] 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.
    • matt-snider 8y ago
      Thanks :-). This comes up so often! Is there a reason HN doesn't use a more mobile-friendly format for preformatted text?
      • stan_rogers 8y ago
        The feature is intended for code, note block quotes. Auto line wraps would be less than helpful.
        • jonsen 8y ago
          Problem is when some text copied and pasted here incidentally starts paragraphs with two or more spaces. And maybe the the commenter does not know why it formats weirdly.
        • deleted 8y ago
          [deleted]
        • frosted-flakes 8y ago
          Yeah, but code blocks are still limited in width on mobile. At least let them flow to the edge of the screen before scrolling.
• tikhonj 8y ago
  The tricky thing with dynamic programming is realizing that it fits—you have to understand how the problem you're solving decomposes into overlapping subproblems that are worth caching. Once you know what the subproblems are, implementing the algorithm is mostly a matter of getting some fiddly indexing logic right. Take string edit distance for example: the key to the dynamic programming problem is seeing how the exponential blow up of possibilities actually has a rich overlapping structure that you can cache in a table. If you didn't know string edit distance was amenable to dynamic programming, you might not realize it at all even if you are constantly thinking about caching results. Once you see the structure, the algorithm becomes relatively straightforward.
  • deepGem 8y ago
    Absolutely, but I attribute the ability to decompose a problem into overlapping subproblems as an understanding of recursion, so I had implicitly assumed such an understanding.
    • baobabKoodaa 8y ago
      Try solving some difficult DP problems on CodeForces. You will find that an "understanding of recursion" is not enough to solve them.
      • eru 8y ago
        No, no, it is an understanding of how to recurse just right. Not an understanding of the concept of recursion in general. Basically, recursion plus memoization is almost the same in terms of power and approach as dynamic programming.
        • baobabKoodaa 8y ago
          No, it's not, and if you actually tried to solve one of the harder DP problems, this would become very obvious to you. Here's one for you: https://codeforces.com/problemset/problem/1097/G https://codeforces.com/problemset/problem/1097/G It's a dp problem, and you understand how to recurse just right, and you understand memoization, so you'll be able to solve it, right? Link your solution when you reply please.
• 01100011 8y ago
  In my "real world" we normally don't care about things like big-O complexity. We worry about doing dumb things and not taking more time than we have available. I'm not saying big-O is useless or CS wizards are never helpful. It's just that you need one or two of them for a large team of normies, IME. I have a problem with this notion that knowledge of algorithms is required to be a good engineer though. Case in point: Senior algorithm nerd on my project is going nuts over algorithmic complexity and delaying an early delivery to another team so they can begin using our new feature. In our case, n is fairly small no matter what, so 2n vs n^2 really doesn't matter to us. The code he's optimizing isn't even the long pole in the tent. It calls other routines which take 2/3 of the total time anyway. We could just deliver now and improve later when we have real world data on how people want to use our feature, but nope, we're wasting time on endless rewrites in search of perfection which may not matter if the other team can't deploy our stuff in time.
  • deepGem 8y ago
    Sadly, Perfectionists share a trait when it comes to building software, obsession to their craft at the expense of everythng else, shipping times included.
    • 01100011 8y ago
      I think we all derive joy from writing 'perfect' software...but then the rules are changed and perfection becomes garbage :) Like the other piece of software I was working on for this project. Nice little test framework with a beautiful OOP structure... which became a noose as soon as I wanted to add a new feature. Now it's this frankenbeast with a weird appendage glued on.
  • collyw 8y ago
    If you really do need to know that stuff, you can read up on it when it's needed. Been programming professionally for over 15 years and have had to use this stuff once that i can remember. Knowing how to design and index a database well is way more useful.
    • 8y ago
• ignoramous 8y ago
  > In the real world we always think about and do such optimizations, be it I/O, disk access or db access That's they key. You've come across caching as a way to optimize for a given metric. Folks who haven't heard of DP aren't aware of using DP techniques such as memoization, for example, to speed up repetitive tasks [0]. Similarly, you might not be aware of many other techniques you haven't come across [1][2] how could you possibly solve those problems in the exact same way? For instance, QuickSort and its variants were PhD thesis worthy, once upon a time (if not now). [0] Not everything is intuitive, DP certainly isn't, imo. As a rule of thumb, naive solutions to a problem are often times intuitive. [1] https://www.xkcd.com/1053/ https://www.xkcd.com/1053/ [2] https://blog.acolyer.org/2015/01/15/the-tail-at-scale/ https://blog.acolyer.org/2015/01/15/the-tail-at-scale/
• albertzeyer 8y ago
  Yes, basically it is exactly that. (For why it is called like that, see other answers; but that's also somewhat irrelevant.) But the main task is to identify how to iteratively / recursively solve the problem and what to cache (and then you should also be able to tell how efficient your solution is). This is the tricky bit. It doesn't matter if you call it DP or whatever. But it matters to be able to come up with efficient solutions for such problems. And this is what companies want to see.
• baobabKoodaa 8y ago
  DP is a general problem solving approach. It's about recognizing which parts of a naive solution have repetition which can be eliminated to improve the time complexity of the solution. Another poster aptly described it as finding states which can be collapsed into one. However you want to think about it, - DP is a general problem solving approach - DP is not limited to any particular implementation detail (like my parent poster attempts with "it's just a simple cache mechanism") - DP is not a "trick" that you can learn and then solve any DP problem If we have a DP solution, we can write it in many ways. We can write it top-down with recursion and memoization, or we can write it bottom-up without memoization. Whether we use memoization in our solution or not is a minor implementation detail. Both solutions are DP. Other posters seem to make a distinction between these two solutions as if they are entirely different and as if the recursive solution is not dp - this is also incorrect. The challenge in DP tasks is about improving time complexity by recognizing repeated sub calculations.
  • reader5000 8y ago
    In "Algorithms" [Dasgupta, Papamdimitriou, Vazirani] they state that the memoization (e.g. querying a hash table) can have significant overhead leading to a large constant factor in the big O analysis. On the other hand, the bottom up approach using a table solves all the possible subproblems including ones that are not needed and ones that the recursive approach would avoid. So from a big O perspective the recursive top-down and the table bottom-up approaches are the same but there can be significant constant factor differences.
    • UncleMeat 8y ago
      Then mention this in the interview. I ask an algorithms question that would likely be hated on HN but when candidates tell me the practical difference (API cleanliness, maintainability, performance, extensibility) between approaches that ultimately don't impact asymptotic runtime I love it.
    • baobabKoodaa 8y ago
      This is true. However, both approaches are "dp" if we are talking about the equivalent solution implemented in these different ways.
• dahart 8y ago
  DP means you map the problem to a grid, and your cache connections are your neighbors on the grid. Memoize (aka caching) was invented later than DP, and it’s easier and the same complexity. You don’t have to map your problem to a spatial layout. One big difference is that DP often involves windowing your cache. While the problem might be on a 2d grid, the storage for your cache might be just two rows, and the algorithm will sweep down rows only once. So, a DP solution might be far less memory than a straightforward memoize, unless you’re doing work to clean up memoize as soon as it’s no longer needed. Another big difference is that with DP you’re pre-allocating, while with memoize you’re typically using dynamic memory allocations by default. That obviously doesn’t have to be true, but makes a fairly naive DP solution faster than a fairly naive memoization.
• JJMcJ 8y ago
  Programming in the wide sense of any list of things to do. Dynamic because it sounds nice. Name was chosen because US Secretary of Defense at the time hated anything that smelled of research, so they found another name. See https://en.wikipedia.org/wiki/Dynamic_programming#History https://en.wikipedia.org/wiki/Dynamic_programming#History Remember, what most of on this board do is computer programming, or perhaps software programming. The people who decide what songs to play on the radio. They are programmers also.
• jahewson 8y ago
  What makes dynamic programming special is that it exploits optimal substructure, where a problem can be broken down into smaller sub-problems, the solution to which must be part of the optimal solution to the larger problem. While caching can be applied anywhere, dynamic programming can only be applied where optimal substructure is present. For example, finding the shortest path between all points in a graph. Likewise, finding the longest path doesn't have optimal substructure and so dynamic programming cannot be applied in that case.