Talk:Dynamic programming/Archive 1

Archive 1

Archive 2

Archive 3

Memoization vs. Dynamic Programming

These are two different approaches, not a tool and a class of problems. This page is perpetuating serious misconceptions. --67.188.230.235 (talk) 19:08, 24 November 2015 (UTC)

I'm not really sure what you mean. In the lede, at least, DP is presented as "a method for solving a complex problem by ...", while memoization is presented as a "technique". (I do agree that memoization, which has its own article, gets a lot of coverage in this one.) QVVERTYVS (hm?) 10:51, 14 February 2016 (UTC)

Memoization can't do the egg dropping puzzle??

This page makes a very bold statement: that there are dynamic programming problems which memoization cannot be used to solve. I supposed there might exist examples of this (though I can't think of any), but the page goes on to claim that the egg dropping puzzle is one of them. The recurrent function is:

W(n,k) = 1 + min{max(W(n − 1, x − 1), W(n,k − x)): x = 1, 2, ..., k }

with base cases at k=1 and n=1. This is straightforwardly (if inefficiently) implemented using a recursive function:

   function W(n,k):
       if n = 1 return 1
       else if k = 1 return k
       else 
           mn = inf
           for x from 1 to k:
               mn = min(mn, max(W(n - 1, x - 1), W(n, k-x)))
           return mn + 1

Thus it's also trivially memoized. What's the issue? What am I missing? — Preceding unsigned comment added by 129.174.124.66 (talk) 16:43, 12 January 2015 (UTC)

The issue is that you did not read the paragraph carefully. It was talking about optimal solutions, specifically algorithms with optimal time complexity (space complexity is usually a secondary concern). Your memoized recursive algorithm is indeed the naive one referred to by the paragraph, which works but does not has optimal time complexity. The section on the egg dropping problem itself gives your solution (though in words rather than pseudo-code) and notes that it takes O(n*k^2) time with a DP solution (which is exactly what yours would take if you use memoization). It even goes on to state how it can be directly improved a little, before giving a faster (but I don't know whether it is optimal) algorithm that uses a totally different parametrization. Lim Wei Quan (talk) 12:50, 9 July 2015 (UTC)

This is misunderstanding perpetuated, unfortunately, by the way CLRS talks about DP. DP is an algorithm design paradigm, not a cure-all. There is no guarantee that the time required by a DP solution be polynomial--indeed, the DP solution to the TSP of Held and Karp (SIAM J., vol. 10 (1962), pp. 196-210) is still the best general TSP algorithm; it is, of course, exponential. I wish CLRS were clearer on this point: it gives the impression that the DP solution, if done right, leads to algorithms in P. I do not understand Lim Wei Quan's reference to "optimal solutions"; how does one know, for example, that the O(n^3) DP solution to matrix chain product is optimal?! I have never seen a proof of that (but would like to). — Preceding unsigned comment added by 73.44.176.246 (talk) 16:02, 18 February 2016 (UTC)

The point I hope was clearly conveyed by the article is that any recursive algorithm is trivially memoized. (In fact some programming languages do that automatically!) As for my statement about optimal solutions, notice that nowhere in the article or on the comments page did I say that any of the presented algorithms are optimal. In my above comment I even expressly state that I do not know whether my solution for the egg-drop puzzle is optimal. But we do know that the naive DP algorithms are often not optimal, and that is the point. In some rare cases we can of course prove optimality, such as if we are required to print out all fibonacci numbers, in which case it is clear that the memoized recursive algorithm takes space and time linear in the output, which is best possible. In many other cases no optimality results are known. Another simple example is finding an element in an n-item sorted list, which requires O(log(n)) key-comparisons, and so binary search is optimal, which is not a memoized recursive algorithm in any reasonably natural way. That is the point of the sentence "Others can be more complicated and cannot be implemented as a recursive function with memoization.". Arguably this sentence is technically false since every algorithm can be written as a recursive function that does not really do any recursion, but it is an attempt to stop students' common misconceptions before they begin, one of which is that DP can solve a lot of problems. No it does not, just as we cannot quite say that recursion solves a lot of problems. They are both just generic techniques and usually need to be used in conjunction with some crucial insights specific to the problem to be solved. I hope that it is all clear now! =) Lim Wei Quan (talk) 10:58, 9 March 2016 (UTC)

Discrete vs Continous, Deterministic vs. Stohastic

If I remember well from the courses I took long time ago dynamic programming comes in different flavors: discrete vs. continuous and stohastic vs. deterministic. Usually, in computer science we just reduce dynamic programming to the deterministic, discrete case.

An example of the continuous dynamic programming that I would like to see in Wikipedia is the solution of the problem of landing on the Moon where one has to minimize the amount of rocket fuel for lunar landing of a space ship. Tomo 12:38, 16 Apr 2005 (UTC)

It's been sometime since the proposal of adding emphasis or an example for continuous problems treated by dynamic programming, but I support this.Hardmath (talk) 14:34, 3 April 2016 (UTC)

Assessment comment

The comment(s) below were originally left at Talk:Dynamic programming/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

The current Wikipedia page on the subject of Dynamic Programming ignores the fact that it has been used a long time before Richard Bellman 'invented' it, by Pierre Masse, Head of Electricite de France' as early as 1944,and has also been applied by JDC Little for optinization of the Grand Coulee Dam's operation, also before Bellman first published papers about Dynamic Programming.

Last edited at 13:34, 15 July 2008 (UTC). Substituted at 13:57, 29 April 2016 (UTC)