Talk:Dynamic programming

Template:Findsourcesnotice

Example

I (FvdP 21:51 Oct 22, 2002 (UTC)) had begun an example but do not feel the motivation to finish it cleanly right now (and perhaps not in the immediate future either). Here is it if anyone wants to complete it::

Suppose that we have to compute the product of n matrices A₁.A₂. ... .A_n, and we want to minimize the total number of operations by executing the matrix products in the best possible order.

The product of two matrices of size i × j and j × k

........

---

This example is published in Cormen's Introduction to Algorithms textbook. Will we run into copyright issues by putting it here?

Absolutely not! Ideas cannot be copyrighted, only a particular way of expressing those ideas. CLRS itself based this section on various papers. In other words, we can write an explanation of the problem and its solution in our own words, but should be careful not to copy text or even the precise presentation of the problem. Derrick Coetzee 20:09, 5 Oct 2004 (UTC)

Confusion

The first paragraph of the second part and the article on algorithms states that dynamic programming is a bottom-up approach, but later this article says dynamic programming may use bottom-up or top-down approaches. --zeno 11:46, 9 Feb 2004 (UTC)

I've revised that section. It was very vague and somewhat incorrect. I hope there's less confusion now. Derrick Coetzee 20:18, 5 Oct 2004 (UTC)

Weirdness

The page says "i dont know" in those terms, which is not only weirdly misplaced, but also improperly formatted. Someone check.

Misplaced section

The part following "The steps for using dynamic program goes as follows:" is out of place. Out of nowhere the article starts using terms like 'gap penalties' and 'sequence alignment.' Seems like this was copied from some article on a specific application, such as protien sequencing. Anon, Wed Jul 11 14:11:43 EDT 2007

Too many examples

This is not a textbook. One good example would suffice. Even worse, many of them are just too long (and boring). Put them in wikibooks. Unfortunately, any attempt to fix this article would be blocked as "vandalism". Way to go, Wikipedia!

Checkerboard

The current „Checkerboard“ section has many problems that make it confusing or outright incorrect. Here are just a few:

1. What is the meaning of the dashes („–“) at positions (1,1), (1,2), (1,4,) (1,5), (2,1) and (2,5) in the checkerboard? The text of the section says „start at any square on the first rank (i.e., row)“. So if an implementation starts at one of the squares that contains dashes, what cost should a dash be given? Or should those positions be ignored when computing the cost? The current explanation does not make that clear.
3. The explanation goes on to say „before computing the cost of a path, we check the array q[i, j] to see if the path cost is already there“. But the pseudo code does not check to see if the path is already there. Instead, the pseudo code unconditionally always computes the path cost and assigns it to the q(i,j) array within the various for loops; none of which ever checks whether or not any costs were computed already.
5. The text refers to „the previous node on the shortest path to s“. The word “node” implies a graph data structure. But the data structure being modeled in the example is explicitly introduced as an array of squares. In my opinion, it is confusing to refer to an array's squares as nodes if it is never explicitly mentioned that a graph data structure is what's being modeled.

I implemented the pseudo code to the best of my understanding. However, it isn't clear whether or not the path my implementation computed (3<-4<-5<-4<-5) is the expected result for the specific checkerboard given in the explanation.

Wouldn't there be some value in including within the explanation the expected solution to the problem that's posed in the explanation?

algoHolic (talk) 17:15, 4 February 2019 (UTC)