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.


1 Answer 1


Before proving a lower bound you have to formalize your computational model. This can be done in several ways for dynamic programming. The pioneer here is Allan Borodin, who came up with priority branching trees. Buresh-Oppenheim et al. extended this to the strong model of priority branching programs. Jukna considered incremental dynamic programming algorithms,tropical circuits and tropical switching networks. The last model is particularly simple, and Jukna proves some tight results for it, so you may be able to prove that your algorithm is optimal for that model.

  • $\begingroup$ thanks, it's very interesting. Far from being obvious, as I suspected. Hope that future introductory books will include something of this theoretical framework. $\endgroup$
    – kentilla
    Feb 1, 2016 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.