algorithm - 伪代码中的负数组索引

Question

考虑 Levenshtein 距离的伪代码示例:

function Leven_dyn(S1[1..m], S2[1..n], m, n);
var D[0..m, 0..n];
begin
  for i := 0 to m do
    D[i, 0] := i;
  end for
  for j := 0 to n do
    D[0, j] := j;
  end for
  for i := 0 to m do
    for j := 0 to n do
      a := D[i - 1, j] + 1;    // here accessing negative index
      b := D[i, j - 1] + 1;    // and here
      c := D[i - 1, j - 1];    // and here
      if S1[i] != S2[j] then
        c := c + 1;
      end if
      if min(a, b, c) = c then
        D[i, j] := c;
      else if min(a, b, c) = a then
        D[i, j] := a;
      else
        D[i, j] := b;
      end if
    end for
  end for
  return D
end

我的第一个想法是它试图访问负数数组的索引，我想这不是故意的行为。

伪代码是否完全错误，嵌套的 for 循环应该从 1 开始？

或者也许伪代码中的负索引在某种程度上与正常的语言相关代码中的负索引不同(例如被忽略或其他)，因此伪代码会很好吗？

Answer 1

一般来说: 大多数编程语言的索引约束不需要也适用于伪代码(即使大多数伪代码不使用负索引)。

但在这种情况下，我认为嵌套循环应该从 1 开始。

代码是计算编辑距离的动态规划实现

前 2 个循环初始化矩阵的上边界和左边界。嵌套循环填充矩阵的内部。

您可以找到此伪代码的大量实现。例如。 https://en.wikipedia.org/wiki/Levenshtein_distance