# Travelling plan between two places

There is a class of DP related problems where you have a set of consecutive steps, say $1 \ldots n$, and two places e.g. $A$ and $B$.

At each step $i$ there are two choices: stay where you are or change. Whatever you choose you pay a cost $A_i$ or $B_i$ depending on where you are, anyway if you change you pay also an addition that is usually a constant value.

For example, in Kleinberg's problem 6.4 you have two cities (New York and San Francisco), a set of $n$ months, a moving cost $M$ and two sequences of operating costs: $N_1 \ldots N_n$ and $S_1 \ldots S_n$. A plan is a sequence of $n$ locations, such that the $i$-th location indicates the city in which you will be based in the $i$-th month. The cost of a plan is the sum of the operating cost of each of the $n$ months, plus a moving cost of $M$ for each time you switch cities. You have to find a plan of minimum cost.

You eventually approach such problems using two variables. For example defining $OPT(i,j)$ with $i \in \left\{1\ldots n\right\}$ and $j\in \left\{N,S\right\}$ as the cost ending up in month $i$ at $j$ city . $$OPT(i,N) = \min\left(N_i + OPT(i-1,N), N_i + OPT(i-1,S) + M \right)$$ $$OPT(i,S) = \min\left(S_i + OPT(i-1,S), S_i + OPT(i-1,N) + M \right)$$

At the end of the process, solution is given by $\min\left\{ OPT(n,N), OPT(n,S) \right\}$.

This is pretty straightforward, but i perceive it as a pragmatic way. How may we prove that two variables are strictly required here? Is there any particular property related to this class of problems?

I'd like to know also if there is a way for solving it with a different recurrence with a variable only, or why if it is not possible.