ДП на префиксах двух строк: как реализовать редакционное расстояние (Левенштейна) за O(nm)?

dp[i][j] = минимальное число операций, чтобы превратить первые i символов a в первые j символов b (ДП на префиксах). Переходы по последнему символу:

• удалить a[i-1]: dp[i-1][j] + 1
• вставить b[j-1]: dp[i][j-1] + 1
• заменить/совпадение: dp[i-1][j-1] + (a[i-1] != b[j-1] ? 1 : 0)

int n = a.size(), m = b.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1));
for (int i = 0; i <= n; ++i) dp[i][0] = i; // удалить i символов
for (int j = 0; j <= m; ++j) dp[0][j] = j; // вставить j символов
for (int i = 1; i <= n; ++i)
  for (int j = 1; j <= m; ++j) {
    int cost = (a[i - 1] == b[j - 1]) ? 0 : 1;
    dp[i][j] = min({ dp[i - 1][j] + 1,        // удаление
                     dp[i][j - 1] + 1,        // вставка
                     dp[i - 1][j - 1] + cost  // замена/совпадение
                   });
  }
// ответ dp[n][m]

Граничные условия — ключ к корректности: dp[i][0]=i (превратить префикс в пустую строку = i удалений), dp[0][j]=j (из пустой строки = j вставок).

Время $O(nm)$, память $O(nm)$ (ужимается до $O(\min(n,m))$ двумя слоями, если восстановление не нужно).