Dynamic programming is a method for designing an algorithm to solve an optimization theory problem by decomposing it into overlapping subproblems and storing their solutions. The optimal value at one state is expressed recursively in terms of the values of states reachable from it, so each subproblem need be solved only once.
For a finite-horizon problem, the terminal values are specified first and backward induction evaluates the remaining states in reverse order using the same optimality relation recursively.
