The principle of optimality says every tail of an optimal trajectory is optimal, so the cost-to-go depends only on the current state. In discrete time that observation becomes an explicit, mechanical recursion — the Bellman equation — that fills in the value function one stage at a time, working backward from the end.

The backward recursion

Take an N-stage problem. The state evolves by a known dynamics x_{k+1} = f(x_k, u_k), each stage incurs a running cost g(x_k, u_k), and the end state is charged a terminal cost \varphi(x_N). Write V_k(x) for the cost-to-go: the least total cost incurred from stage k onward, starting in state x.

Step 1 — the terminal condition. At the last stage nothing remains to be decided, so the cost-to-go is just the terminal charge:

Step 2 — one stage of the recursion. Standing in state x at stage k, picking control u costs g(x, u) right now and moves you to f(x, u), from where — by the principle of optimality — the best you can do is V_{k+1}(f(x, u)). Choosing u to minimise the sum gives Bellman's equation:

Step 3 — record the minimiser. The control that attains the minimum is the optimal action at (x, k):

Collecting \mu_k^\* over every state and stage gives the optimal feedback policy — a lookup table of "what to do in each state" — which is far more than the maximum principle's single open-loop trajectory. We sweep k = N, N-1, \dots, 0, each stage built from the one already solved.

A fully worked example

Let the state be x \in \{0, 1, 2\}, with two controls u \in \{0, 1\} and dynamics x_{k+1} = \min(x + u,\, 2) (you may step up by one, capped at 2). The running cost is g(x, u) = x + 2u — occupying a higher state costs more, and each step up costs 2 — while the terminal cost \varphi(x) = 4(2 - x) rewards finishing high. There are N = 2 stages, and we start at x_0 = 0.

Stage 2 — terminal. V_2(x) = \varphi(x) = 4(2 - x):

Stage 1. Apply V_1(x) = \min_u[\, g(x, u) + V_2(\min(x+u, 2)) \,] at each state:

Stage 0. Now apply V_0(x) = \min_u[\, g(x, u) + V_1(\min(x+u, 2)) \,], reusing the stage-1 values:

Read off the optimal run. From x_0 = 0 the optimal cost is V_0(0) = 5. The policy says: at stage 0 play \mu_0^\*(0) = 1, moving to x_1 = 1; at stage 1 play \mu_1^\*(1) = 1, moving to x_2 = 2. The trajectory 0 \to 1 \to 2 costs g(0,1) + g(1,1) + \varphi(2) = 2 + 3 + 0 = 5, matching V_0(0) exactly.

The table, filling backward

Here is that computation as a table — one column per stage, one row per state. Slide backward stages computed: the terminal column V_2 = \varphi appears first, then V_1, then V_0, each built from the column to its right. The small u^\* under each computed cell is the optimal action there; tracing them from x_0 = 0 gives the optimal run.