Let’s prove that optimal route has the following form:
1 < a_1 < a_2 < \ldots < n > b_1 > b_2 \ldots > 1.
To prove it, consider some optimal route. Let’s delete n from it for now and let’s try to insert it to some place in a route. If we are inserting between x < y, we are substracting weight of edge xy and adding weights of edges xn and yn. So, it will increase value by (n - x)D + c_{xn} + (n - y)D + c_{yn} - (y - x)D - c_{xy}= 2(n - y)D + c_{xn} + c_{yn} - c_{xy}
We can see that
2(n - y) - D \lt 2(n - y)D + c_{xn} + c_{yn} - c_{xy} \lt 2(n - y)D + 2D.
From that we can see that it always optimal to place n near n - 1.
With the same reasoning, we can show that n - 2 will be near the segment of n and n - 1(by deleting segment of n and n - 1 and couting contribution after inserting it between x and y).
So, it follows that each time we will insert smallest number either to the left, or to the right, so route indeed has such form.
Knowing the form of the optimal answer, we can write dynamic programming dp[x][y] -suppose that we have placed numbers from x to n and numbers on the border are x(it will be also on the border) and y, what’s the minimal length in this case? Then, we can add x - 1 to either left or right border, and update values by the following rules:
- dp[x - 1][x] = min(dp[x - 1][x], dp[x][y] + weight_{x - 1 y})
- dp[x - 1][y] = min(dp[x - 1][y], dp[x][y] + weight_{x - 1 x})
Where weight_{ab} denotes length of the edge ab.
Complexity of our solution is O(n^2).