Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of and optimal substructure. When applicable, the method takes far less time than naive methods that don't take advantage of the subproblem overlap.

The idea behind dynamic programming is quite simple. In general, to solve a given problem, we need to solve different parts of the problem (subproblems), then combine the solutions of the subproblems to reach an overall solution. Often when using a more naive method, many of the subproblems are generated and solved many times. The dynamic programming approach seeks to solve each subproblem only once, thus reducing the number of computations: once the solution to a given subproblem has been computed, it is stored: the next time the same solution is needed, it is simply looked up. This approach is especially useful when the number of repeating subproblems exponential growth as a function of the size of the input.

Linear programming adopts an intentionally simple model. Dynamic programming concerns itself with a class of functional relations that arise from multi-stage decision processes possessing certain definite structural characteristics. Thecharacteristic properties are exploited to effect a reduction in the dimensionality of the mathematical problem, thereby making some complex processes amenable to analytic or computational techniques.

Since linear programming is an allocation problem, various subproblems (states) may be defined as the amount of resources to be allocated to the current stage and the succeeding stages. This will result in a backward functional (recursive) equation, which, when obtained, can be used to solve the linear programming problem by the dynamic programming approach.