Вы читали http://www.merriampark.com/ld.htm?
Вы рассчитываете стоимость преобразования - количество вставок и удалений - необходимое для преобразования одной строки в другую.
Эта «стоимость» преобразования указывает расстояние между двумя строками.
А как насчет бирж? Это алгоритм Дамерау – Левенштейна , который отличается. Включение обменов не сильно улучшает ситуацию.
Суть в том, чтобы создать матрицу между двумя словами и вычислить - столбец за столбцом - «расстояние» от каждой буквы каждого слова до каждой буквы другого слова. Нижний правый угол этой матрицы - это общее расстояние с учетом всех букв.
Вопрос 1)
Ячейка "выше" отражает историю изменений, и символ для этой строки (обычно) отличается от этого, поэтому эта ячейка является удалением относительно нее.
Ячейка "слева" отражает историю изменений, и символ для этого столбца (обычно) отличается от этого, поэтому эта ячейка является вставкой относительно нее.
Единственный раз, когда это обычно неправильно, это слова с трехбуквенной последовательностью. Редко на английском.
Сравнение строк и столбцов имеет стоимость 0 или 1.
Минимальная сумма «история плюс одно изменение» и фактическая стоимость изменения являются применимой стоимостью.
Вопрос 2)
Переменные i и j не являются длинами чего-либо. Они позиции в матрице сравнения. «Вставка» и «удаление» - это действие, необходимое для преобразования одного слова в другое. Количество действий вставки / удаления - это расстояние между словами.