Formal Description​

s_i - denotes the state of the system at i^th time, for all i = 1, 2, …, n (state transitions).

x_i - denotes the decision made at i^th time for all i = 1, 2, …, n.

                  

                                                           Figure 1

In other words, for all i = 1,2,…,n-1, the state transitions are denoted as:

                  

Let the cost of the changing state from s_i to s_i=1 be denoted as g_i(s_i,x_i)

Then the total cost is given as:

                  

Design Methodology for DP

Four step method:

1. Characterize the Bellman equation for the problem.
2. Recursively find the optimal solution and itscorresponding value for each tail problem.
3. Compute the value of an optimal solution in a bottom-upfashion.
4. Construct an optimal solution from computedinformation.

              The Squid