I am struggling with the following dynamic programming problem:
Given a complete $N$ vertex digraph and a list of vertices $List$, find a way for two players who start at vertices 1 and 2 respectively to visit each vertex from $List$ (order matters, i.e. $List_{i + 1}$ should be the vertex visited after $List_i$). Some vertices may appear in $List$ more than once (multiset). It is sufficient for a vertex to be visited by only one of players (i.e. one of them can visit all vertices while the other would remain at his starting position) If one player makes a move, the other stands still (can't make moves in parallel). If the current vertex to be visited is $List_i$, players must move to it directly, i.e. take either $(List_{i - 1}, List_i)$ edge (since the previous move guarantees one of player is in $List_{i - 1}$) or $(List_j, List_i)$, for some $j < i$ ($List_j$ is the position other player stopped at during some previous move). This means the path with $L$ vertices in it consists of exactly $L$ edges. The weight/cost of the path should be minimal. Weight of edge $(i, i)$ is always $0$, all weights are non-negative integers, no multi-edges or loops are allowed. Output the cost of such a path.
This is actually a problem from a Russian online judge. The original problem has three players (starting at $1, 2, 3$) in it and also asks to output what player did visit $List_i$, but I reduced the problem for the case of two players which should just make things easier for perception. I think according to the rules I should provide the link for the source problem even if this is a Russian language only website, so here it is http://informatics.mccme.ru/moodle/mod/statements/view.php?chapterid=3379 . If someone really needs it, the stated constraints (that shouldn't matter since we are talking about a simplified version of a problem) for the original problem are $(3 \leq N \leq 200)$ and the number of vertices to be visited is at most $1000$ (I swapped denoting letters), no memory/time limits are given.
The problem has a 2D dynamic programming tag.
My thoughts would be to denote $dp_{i, j}$ as a shortest path that visits vertices from $List_i$ to $List_j$, i.e. $(List_i, List_{i + 1}, ...,List_{j - 1}, List_j)$. The answer is would be stored in $dp_{1, L}$, provided that indexing goes from $1$ and $L$ stands for the length of the $List$. The problem is that I don't have a clear idea how to compute this dp-table. I thought of doing someting like $dp_{i, j} = \min_{k \in i..j}\{ dp_{i,k - 1} + cost(k - 1, List_k) + cost(List_k, k + 1) + dp_{k+1,j}\}$. Naturally, I'd at first compute all paths of length 2, then 3 and so on. The thing is, I don't understand how to deal with the main 'problem' of this problem, determining when the move is made by player 1 or 2. I thought there would probably have to be different costs of paths for different players, but they actually use the same graph, so all that matters is the position player $x$ ended up at. Filling the DP-table would actually have to consider two cases, the one described above which is guaranteed to exist as in path $dp_{i,k - 1}$ we know that one of players ended up in vertex $k - 1$. The case where the other player goes from 'some previous' vertex should be taken into consideration as well, $\min\{ dp_{i,k - 1} + cost(j, List_k) + cost(List_k, k + 1) + dp_{k+1,j}\}$ , where $j$ stands for 'some previous' vertex. While writing this, I also realized that I'd probably need a little hint how to remember the player that visited vertex $List_i$ which is needed for the original problem.
Could you provide me some help please?
