Talk:Dynamic programming

This  level-5 vital article is rated B-class on Wikipedia's content assessment scale.
It is of interest to the following WikiProjects:Computer science Top‑importance

	This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Top	This article has been rated as Top-importance on the project's importance scale.
Things you can help WikiProject Computer science with: Here are some tasks awaiting attention: Article requests : Requested articles/Applied arts and sciences/Computer science, computing, and Internet Cleanup : Computer science articles needing attention Computer science articles needing expert attention Copyedit : Computing Expand : Computer science Infobox : Computer science articles without infoboxes Maintain : Timeline of computing 2020–present Photo : Find pictures for the biographies of computer scientists (see List of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

Molecular Biology: COMPBIO

	This article is within the scope of WikiProject Molecular Biology, a collaborative effort to improve the coverage of Molecular Biology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
???	This article has not yet received a rating on the importance scale.
	This article is supported by the Computational Biology task force (assessed as Top-importance).

Systems High‑importance

	This article is within the scope of WikiProject Systems, which collaborates on articles related to systems and systems science.
High	This article has been rated as High-importance on the project's importance scale.
	This article is within the field of Control theory.

Mathematics Mid‑priority

	This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mid	This article has been rated as Mid-priority on the project's priority scale.

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!

Why ALGOL

Hello , in

function fib(n)

   if n <= 1 return n
   return fib(n − 1) + fib(n − 2)

I doubt that the return function would return a false if, so maybe you make a if n larger or equal to 1 out of it ? That also has the nice side effect that the Fibonacci numbers would become larger than -1, like the original series is larger than +1, I guess that is what you intended ...

Approach to this article

I think this article suffers from bush-beating which is a common feature of computer language theory articles. If one closely examines the literature on DP, and compares it to algorithms for converting recursive programs into iterative (and thus, forgetful) programs, one will see a lot of overlap. The introduction here doesn't quite do the topic credit with words like 'paradigm' or 'optimization method'. It's an algorithm itself, and it operates on recursively defined data. That's concrete. You convert each sub-problem to also return its intermediates, then convert all sub-problems to re-usages of returned intermediates. Rinse and repeat. If the substructure is optimal, you get the optimum.

DP should be a reliable device in your brain, but this article contributes greatly to the nebular thinking about it. This device is really important because it comprehensively solves a key problem and reminds people to observe limits of applicability. 184.19.20.241 (talk) 12:47, 1 October 2023 (UTC)

I'd also like to add that Bellman's equation (although possibly correct, hard to tell) is completely overloaded for the purpose and that optimal substructure is the correct condition for optimality of DP. Concerns about infinite problems are addressed by noting that DP can apply to both numerical and symbolic computations. When DP is applied to data that define symbolic terms, that's how you do it with infinite and continuous objects. 184.19.20.241 (talk) 13:11, 1 October 2023 (UTC)