In addition to dynamic programming terminology, we can also use mathematical notation to describe any dynamic programming problem. This helps us to set up and solve the problem. Consider stage 2 in the George Yates dynamic programming problem first discussed in Section M2.2. This stage can be represented by the diagram shown in Figure M2.7 (as could any given stage of a given dynamic programming problem).

As you can see, for every stage, we have an input, decision, output, and return. Look again at stage 2 for the George Yates problem in Figure M2.6. The input to this stage is $s_2,$ which consists of nodes 2, 3, and 4. The decision at stage 2, or choosing which arc will lead to stage 1, is represented by $d_2.$ The possible arcs or decisions are 4–5, 3–5, 3–6, 2–5, and 2–6. The output to stage 2 becomes the input to stage 1. The output from stage 2 is $s_1.$ The possible outputs from stage 2 are the exiting nodes, nodes 5 and 6. Finally, each stage has a return. For stage 2, the return is represented by $r_2.$ In our shortest-route problem, the return is the distance along the arcs in stage 2. These distances are 10 miles for arc 4–5, 12 miles for arc 3–5, 6 miles for arc 3–6, 4 miles for arc 2–5, and 10 miles for arc 2–6. The same notation applies for the other stages and can be used at any stage. In general, we use the following notation for these important concepts:

You should note that the input to one stage is also the output from another stage. For example, the input to stage 2, $s_2,$ is also the output from stage 3 (see Figure M2.7). This leads us to the following equation:

The final concept is transformation. The transformation function allows us to go from one stage to another. The transformation function for stage 2, $t_2,$ converts the input to stage 2, $s_2,$ and the decision made at stage 2, $d_2,$ to the output from stage 2, $s_1.$ Because the transformation function depends on the input and decision at any stage, it can be represented as $t_2 \left(s_2, d_2\right).$ In general, the transformation function can be represented as follows:

The following general formula allows us to go from one stage to another using the transformation function:

Although this equation may seem complex, it is really just a mathematical statement of the fact that the output from a stage is a function of the input to the stage and any decisions made at that stage. In the George Yates shortest-route problem, the transformation function consists of a number of tables. These tables show how we could progress from one stage to another in order to solve the problem. For more complex problems, we need to use dynamic programming notation instead of tables.

Another useful quantity is the total return at any stage. The total return allows us to keep track of the total profit or costs at each stage as we solve the dynamic programming problem. It can be given as follows: