Dynamic Programming 

Dynamic Programming refers to a very large class of algorithms. The idea is to break a large problem down (if possible) into incremental steps so that, at any given stage, optimal solutions are known to subproblems. When the technique is applicable, this condition can be extended incrementally without having to alter previously computed optimal solutions to subproblems. Eventually the condition applies to all of the data and, if the formulation is correct, this together with the fact that nothing remains untreated gives the desired answer to the complete problem. It is often the case in D.P. that the intermediate desirable condition implies more than seems to be strictly needed for the final answer. For example, the lineartime Fibonacci function, recursive or iterative, could be said to be a DPA. It holds (at least) two values, fib(i1) and fib(i). When `i' gets to `n', only one of these values is needed, fib(i)=fib(n). However it is possession of the two values that allows the lineartime algorithm. Examples of dynamic programming include


↑ © L. Allison, www.allisons.org/ll/ (or as otherwise indicated). Created with "vi (Linux)", charset=iso88591, fetched Sunday, 03Mar2024 02:23:14 UTC. Free: Linux, Ubuntu operatingsys, OpenOffice officesuite, The GIMP ~photoshop, Firefox webbrowser, FlashBlock flash on/off. 