Dynamic programming is an algorithmic method that applies solutions to larger and larger cases to inductively solve a computational problem for a given instance. These smaller solutions are typically stored in a "lookup table," which can be consulted when the smaller solutions are needed.
In order to apply dynamic programming, the problem at hand must have the property that finding an optimal solution for smaller cases will guarantee their extension to optimal solutions for larger cases.
A simple example of dynamic programming is applied to the calculation of Fibonacci numbers,
which are counted by the recurrence relation
