Definition:A general class of algorithms which solve problems by solving smaller versions of the problem, saving the solutions to the small problems, and then combining them to solve the larger problem. Thus, dynamic algorithms usually trade space for increased speed.

Sometimes, a divide and conquer approach seems appropriate but fails to produce an efficient algorithm. Therefore, instead of dividing the large problem into two (or more) smaller problems and solving those problems (as done in a divide and conquer approach), dynamic algorithms start with the simplest possible problems. Solutions are usually trivial and the results are stored in simple data structures (i.e. variables, arrays, or tables). These results are then used to solve slightly larger problems, which are saved and used to solve larger problems again. Problems are solved and stored only when they are encountered for the first time.

More information can be found at: http://swww.ee.uwa.edu.au/~plsd210/ds/dynamic.html

Author: John Morris morris@ee.uwa.edu.au

[QuickPerm] | [EXAMPLE 02] | [EXAMPLE 03] | [EXAMPLE 04] | [MetaPerm]

[Download the Five C++ Examples] | [Permutation Exercises]

[Contact the Author] | [Make a Donation] | [Links]

[HOME]

Help keep public education alive! We need your donations, click here to help now...

{top}