作为论文中的伪代码
4. If k = −D or k ≠ D and V[k − 1] < V[k + 1] Then
5. x ← V[k + 1]
6. Else
7. x ← V[k − 1]+1
8. y ← x − k
第 4 行表明，如果 k 不是 -D 或 D，则取 x 较大的那个，而不是找出蛇。这让我很困惑，我不应该同时计算 v[k-1] 和 v[k+1] 并找出哪条路径更远吗？如果我选择 x 较大的那个作为起点，而我们的点会导致更远的路径怎么办？
更重要的是，据此：
即，在对角线 k 中进一步到达 (x',y'+1)和(x"+1,y")，然后沿着对角线边缘直到不再可能这样做或直到编辑的边界图达到。
我认为作者建议应该计算 (x',y'+1) 和 (x"+1,y") （在这种情况下，v[k-1] 和 v[k+1]）。
所以知道我错过了什么吗？
我认为论文遗漏了一个证明，这很简单，但我认为遗漏会导致一些混乱（对我来说），所以我在这里给出这个证明：
在第 6 页第 4 行中，代码如下：
f k = −D or k ≠ D and V[k − 1] < V[k + 1] Then
x ← V[k + 1]
Else
x ← V[k − 1]+1
我不认为 lemma2 会导致这种情况，lemma2 的目的是证明这个问题可以用贪心策略来解决。并且根据Given the endpoints of the furthest reaching (D − 1)-paths in diagonal k+1 and k−1, say (x’,y’) and (x",y")
respectively, Lemma 2 gives a procedure for computing the endpoint of the furthest reaching D-path in diagonal k.
Namely, take the further reaching of (x’,y’+1) and (x"+1,y") in diagonal k and then follow diagonal edges until it is
no longer possible to do so or until the boundary of the edit graph is reached.正常的方法是获取从v[k - 1]和延伸的两个点，v[k + 1]并找出哪个是更远的到达路径。但这会导致双标。这是为什么只有检查有效的证明V[k − 1] < V[k + 1]：
引理4：如果v[k - 1] < v[k + 1]，则v[k + 1]带有一条蛇的垂直边缘的路径将是对角线k 中进一步向后弯曲的路径。
证明：让我们做v[k - 1]tox1和v[k + 1]to x2。所以x1对角线k后面的点是(x1 + 1, x1 + 1 - k)（往右走），后面的点x2是(x2, x2 - k)（往下走）；y 位置在这里没用。那么问题变为：if x1 < x2, then x1 + 1 <= x2
既然x1 < x2 -> x2 - x1 > 0
假设x1 + 1 > x2，那么x2 - x1 < 1，那么0 < x2 - x1 < 1。但是在编辑图中，基本的移动是1，0 < x2 - x1 < 1永远不会发生，所以假设是错误的，所以x1 + 1 <= x2.
我已经在https://github.com/psionic12/Myers-Diff-in-c-/blob/master/README.md上发布了这个和一个实现，欢迎大家讨论。