OPTIMAL SOLUTION: Suppose that you want the trade route to start in city ~x~. It can only progress to its neighbor city on the left or on the right, because any other connection would divide the lake into two regions with unreached cities on both sides, making the construction of a non-crossing trade route impossible. Similar reasoning can be applied to the following cities. Every new city must be adjacent to the already connected cities. In this way, it can only be chosen between the two cities that are adjacent to the already connected ones.

It can also be seen that once you have a set of cities connected with a route that ends in city ~y~ it really doesn't matter the order in which the cities were connected. For example, let's say that you have a route that connects cities ~2~, ~3~, ~4~ and ~5~ and ends in city ~5~. It doesn't matter if the route goes ~2 \to 3 \to 4 \to 5~, ~3 \to 2 \to 4 \to 5~ or ~4 \to 3 \to 2 \to 5~. For any of the previous routes, the two cities that can be chosen next are either ~1~ or ~6~. This situation is distinctive of dynamic programming.

For any pair of cities ~(u,v)~ we say that ~left(u,v)~ is true if it is possible to construct a route that connects every city to the left of a line drawn from ~u~ to ~v~, including ~u~ and ~v~ that ends in ~v~. Also we say that ~right(u,v)~ is true if it is possible to construct a route that connects every city to the right that ends in ~v~. We initialize the recursion stating that for every ~i~, ~left(i,i) = right(i,i) = true~. The recursion formulas are:

$$\displaystyle \begin{align*} left(u,v) &= (left(u,v-1)\text{ and }agreement(v-1,v))\text{ or }(right(v-1,u)\text{ and }agreement(u,v)) \\ right(u,v) &= (right(u,v+1)\text{ and }agreement(v+1,v))\text{ or }(left(v+1,u)\text{ and }agreement(u,v)) \end{align*}$$

If you find a pair of cities ~(i,j)~ for which ~(right(i,j)\text{ and }left(i+1,j)) = true~, you have a solution. The route can be reconstructed easily using the same recursion.