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.

Two-Person Traversal of a Sequence of Cities. You are given an ordered sequence of n cities, and the distances between every pair of cities. 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.

Recursion Relation: We recurse on C(i; j), the minimum distance traveled if person A ends at city
i and person B ends at city j. Assume WLOG i < j. The relation is:
{ to j-1 //end
{ sum d(k, k + 1) if i = 0
{ for (k=1) //start
C(i; j) =
{ min 0
where d(i; j) is the distance between cities i and j.
Running Time: There are n2 entries in C(i; j) and lling in each entry takes O(n) for a total of O(n3).

Refrence http://people.csail.mit.edu/bdean/6.046/dp/
http://courses.csail.mit.edu/6.006/fall10/handouts/dpproblems-sol.pdf