Constraints in Dynamic programming

Question

I am reading Dynamic programming using MIT OCW applied mathematics programming here.

An elementary example is given there in 11.1 as shortest delay to reach parking slot from home. The objective function is having following constraint as we move backward as :

$$ s_{n-1} = \begin{cases} s_n+1, & \text{if we choose up and $n$ is even } \\ s_n-1 , & \text{if we choose down and $n$ is odd } \\ s_n , & \text{otherwise} \end{cases} $$

I am not able to understand this constraint and why we are adding/ subtracting 1 while it is even/odd ?

Answer 1

It's just got to do with the indexing and the picture here. Check out Figure 11.1; each column is a stage $n$, starting at $0$ for the far right and $5$ for the far left. The states $s_n$ are counted from the bottom up starting from $1$ going up to $6$, and the value at each state $t_n(s_n)$ is the number inside the node. For example, $t_0(1) = 3$ because $n=0$ is the far right column, and $s_n=1$ is the bottom state in that column, and the bottom right node has the number $3$ in it. Another example, $t_2(5) = 9$.

The transition function tells you what the next state is based on the current state and the decision. The current state, as before, is an integer from $1$ to $6$, and the decision is up or down (which branch you take to go from one column to the next). Note that, in the picture, the even columns are staggered higher, while the odd ones are lower. If you are in an even column and take the upper branch, the state number will go up by one. If you are on an odd column and take the lower branch, the state number will go down by one. However, if you are in an odd column and you take the upper branch, the state number will stay the same, as it will if you are in an even column and take the upper branch.