Dynamic Programming - Dynamic Algorithms

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.