动态规划：城市遍历

我遇到了这个问题：

有两个人。有 n 个城市的有序序列，并且每对城市之间的距离是给定的。您必须将城市划分为两个子序列（不一定是连续的），使得人 A 访问第一个子序列中的所有城市（按顺序），人 B 访问第二个子序列中的所有城市（按顺序），并且使得A 和 B 行驶的总距离最小。假设A和B最初从各自子序列中的第一个城市开始。

我寻找它的答案，答案是：
设 c[i,j] 为第一个人停在城市 i、第二个人停在城市 j 时所行驶的最短距离。假设 i

c[0,j]= k 从 1 到 j-1 的 (d[k,k+1]) 之和
c[i,j] = min(c[k,j]+ d[k,i]) 如果 i!=0 其中 0

解决方法也可参见第10题here http://courses.csail.mit.edu/6.006/fall10/handouts/dpproblems-sol.pdf

现在，我的问题是：
1. 该解没有 i=1 的定义（因为此时 k 没有值）。
2. 现在，假设我们正在寻找 c[2,3]。它将是 c[1,3]+ d[1,2]。现在 c[1,3] 表示人 B 访问了 0、2 和 3，而 A 保留在 1 或 B 访问了 2、3 和 A 访问了 0 和 1。另外，c[2,3] 表示 A 只访问了 2/ 0,1,2 /0,2 /1,2。所以，

 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])

可以看出，解决方案并不重叠。

换句话说，2已经被c[1,3]中的B覆盖了。因此，如果我们将 c[1,3] 包含在 c[2,3] 中，则意味着 A 和 B 都访问了 2，这不是必需的，因为它只会增加成本。

如果我错了，请纠正我。

Q:: 两人遍历一系列城市：给你一个由 n 个城市组成的有序序列，以及每对城市之间的距离。设计一种算法，将城市划分为两个子序列（不一定是连续的），使得 A 访问第一个子序列中的所有城市（按顺序），B 访问第二个子序列中的所有城市（按顺序），并且A 和 B 行驶的总距离最小。假设A和B最初从各自子序列中的第一个城市开始。

这是我对解决方案的理解：:

假设城市的编号是从 1 到 n。我们在 C(i, j) 上递归，即人 A 在城市 i 结束而人 B 在城市 j 结束时行驶的最短距离。不失一般性地假设 i

令 C(0, n) 表示人 A 没有访问任何城市，而人 B 访问 [1, n] 中的所有城市。

因此，C(0, j) = d(1,2) + d(2,3) + .... + d(j-1, j) （B从城市1开始，依次到城市j） 。

C(i, j)，其中 i 不为 0 = 以下两种情况的最小值：

情况1：A人在i城市出发和结束。此时，C(i, j) = 人 B 行驶的距离，按顺序前往从 1 到 j 的所有城市，跳过城市 i = d(1,2) + d(2,3) + ... + d(i-1, i+1) + d(i+1, i+2) + ... + d(j-1, j)

情况2：人A在i之前从某个城市出发，因此他在前往城市i（其遍历中的倒数第二个城市）之前经过了一个城市k。在这种情况下，C(i, j) = 最小值 {C(k, j) + d(k, i)}，其中 k 可以在 1 到 i-1 之间变化。

该问题的解是最小值 { C(i,n) }，其中 i 从 0 变化到 n-1。

我们可以按行主序填充 DP 矩阵，因为 C(i,j) 的每次计算都需要距离 d 或 C(k,j)（其中 k

该算法的运行时间将为 O(n^3)，因为我们要计算 O(n^2) 个条目，并且每个计算需要 O(n) 时间。

编辑:: 我认为讲义中给出的解决方案缺少 case1。