Изменения

Алгоритм в виде, описанном выше, требует <tex>\Theta(M \cdot N)</tex> операций и такую же память, однако, если требуется только расстояние, легко уменьшить требуемую память до <tex>\Theta(N)</tex>. Заметим, что для вычисления <tex>D[i]</tex> нам нужно только <tex>D[i - 1]</tex>, поэтому будет будем вычислять <tex>D[i]</tex> в <tex>D[1]</tex>, а <tex>D[i - 1]</tex> в <tex>D[0]</tex>. Осталось только поменяем поменять местами <tex>D[1]</tex> и <tex>D[0]</tex>.