Editing Dynamic programming (section)

=== Mathematical optimization ===
In terms of mathematical optimization, dynamic programming usually refers to simplifying a decision by breaking it down into a sequence of decision steps over time.

This is done by defining a sequence of '''value functions''' ''V''<sub>1</sub>, ''V''<sub>2</sub>, ..., ''V''<sub>''n''</sub> taking ''y'' as an argument representing the '''[[State variable|state]]''' of the system at times ''i'' from 1 to ''n''.

The definition of ''V''<sub>''n''</sub>(''y'') is the value obtained in state ''y'' at the last time ''n''.

The values ''V''<sub>''i''</sub> at earlier times ''i''&nbsp;=&nbsp;''n''&nbsp;&minus;1,&nbsp;''n''&nbsp;&minus;&nbsp;2,&nbsp;...,&nbsp;2,&nbsp;1 can be found by working backwards, using a [[Recursion|recursive]] relationship called the [[Bellman equation]].

For ''i''&nbsp;=&nbsp;2,&nbsp;...,&nbsp;''n'', ''V''<sub>''i''&minus;1</sub> at any state ''y'' is calculated from ''V''<sub>''i''</sub> by maximizing a simple function (usually the sum) of the gain from a decision at time ''i''&nbsp;&minus;&nbsp;1 and the function ''V''<sub>''i''</sub> at the new state of the system if this decision is made.

Since ''V''<sub>''i''</sub> has already been calculated for the needed states, the above operation yields ''V''<sub>''i''&minus;1</sub> for those states.

Finally, ''V''<sub>1</sub> at the initial state of the system is the value of the optimal solution. The optimal values of the decision variables can be recovered, one by one, by tracking back the calculations already performed.