title: dynamic programming : traversal of cities
body: <p>I came across this question:</p>
  
  <p>There are two persons. There is an ordered sequence of n cities, and the distances between every pair of cities is given. You must partition the cities into two subsequences (not necessarily contiguous) such that person A visits all cities in the first subsequence (in order), person B visits all cities in the second subsequence (in order), and such that the sum of the total distances travelled by A and B is minimized. Assume that person A and person B start initially at the first city in their respective subsequences.</p>
  
  <p>I looked for its answer and the answer was:<br>
  Let c[i,j] be the minimum distance travelled if first person stops at city i and second at city j. Assume i&lt; j </p>
  
  <p>c[0,j]= summation of (d[k,k+1]) for k from 1 to j-1<br>
  c[i,j] = min(c[k,j]+ d[k,i]) if i!=0 where 0
  
  <p>The solution can also be seen at question 10 <a href="http://courses.csail.mit.edu/6.006/fall10/handouts/dpproblems-sol.pdf" rel="nofollow">here</a> </p>
  
  <p>Now, my problems are:<br>
  1. This solution has no definition for i=1 (as then k has no value).<br>
  2. Now, suppose we are finding c[2,3]. It would be c[1,3]+ d[1,2]. Now c[1,3] means person 
     B visited 0, 2 and 3 and person A remained at 1 or person B visited 2 and 3 and A 
     visited 0 and 1. Also, c[2,3] means A visited just 2/ 0,1,2 /0,2 /1,2.  So,</p>
  
  <pre><code> c[1,3] = min(d[0,1]+ d[2,3], d[0,2]+ d[2,3])
   c[2,3] = min(d[0,1]+ d[1,2], d[0,2]+ d[1,3], d[1,2]+d[0,3], d[0,1]+d[1,3])
  </code></pre>
  
  <p>As can be seen the solutions are not overlapping.</p>
  
  <p>To put it in other way, 2 is already covered by B in c[1,3]. So if we include c[1,3] in c[2,3] it would mean that 2 is visited by both A and B which is not required as it would just increase the cost.</p>
  
  <p>Please correct me if I am wrong.</p>