Расстояние редактирования определяется следующим образом:
Для двух слов word1 и word2 найдите минимальное количество операций, необходимых для преобразования word1 в word2.
У вас есть следующие 3 операции, разрешенные для слово:
- вставить символ
- удалить символ
- заменить символ
Эту проблему можно решить с помощью динамического программирования c. Но я не совсем понимаю правило индукции dp[i][j] = dp[i-1][j-1], когда word1[i] == word[j].
Я думал, что правило индукции должно быть
dp[i][j] = min { dp[i-1][j-1], dp[i][j-1] + 1, dp[i-1][j] + 1 }
Согласно правильному правилу индукции, кажется, что dp[i-1][j-1] всегда минимально среди трех. Но мне трудно доказать это.
Я попробовал следующую логику c, чтобы доказать dp[i-1][j-1] <= <code>dp[i][j-1] + 1:
Один способ конвертировать word1[0:i-1] в word2[0:j-1] добавляется символ word[j] к word2[0:j-1], а затем конвертируется word1[0:i-1] в word2[0:j].
Но проблемы с этим подходом:
(1 ) Этот подход работает на word2, хотя я хочу работать только на word1.
(2) Даже после преобразования word1[0:i-1] в word2[0:j], есть еще один шаг, необходимый для преобразования его в word2[0:j-1]
Может кто-нибудь дать подсказку, как это доказать? Спасибо!