Edit distance с разной ценой операций: как обобщить рекуррентность Левенштейна?
В обычном расстоянии Левенштейна вставка/удаление/замена стоят по 1. Но в задаче у операций РАЗНЫЕ цены: вставка ci, удаление cd, замена cr. Как переписать переход и базу? И что, если замена дороже, чем удалить+вставить?
2 ответа
Обобщение прямое — в переходе подставляем стоимости вместо единиц:
int n = a.size(), m = b.size();
vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
dp[0][0] = 0;
for (int i = 1; i <= n; i++) dp[i][0] = (long long)i * cd; // удалить i символов
for (int j = 1; j <= m; j++) dp[0][j] = (long long)j * ci; // вставить j символов
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1]; // совпало — бесплатно
else dp[i][j] = min({
dp[i-1][j] + cd, // удалить a[i-1]
dp[i][j-1] + ci, // вставить b[j-1]
dp[i-1][j-1] + cr // заменить
});
}
long long ans = dp[n][m];
Сложность O(n·m) время и память. Ключ — база теперь не i и j, а i*cd и j*ci (стоимость удалить весь префикс / вставить весь префикс). Самая частая ошибка — оставить базу как dp[i][0]=i, забыв домножить на цену, → WA.
Про «замена дороже, чем удалить+вставить»: формально замену можно эмулировать как удаление + вставка ценой cd + ci. Чтобы алгоритм автоматически выбирал дешёвейший вариант, можно просто заменить cr на min(cr, cd + ci) — тогда переход сам предпочтёт удалить+вставить, если так дешевле. Но в стандартном ДП это и так учтено: путь dp[i-1][j] + cd затем dp[i][j-1] + ci тоже рассматривается через соседние клетки, так что явная эмуляция не обязательна. Просто следи, чтобы все c* были long long, если строки длинные — суммарная цена может переполнить int.