Наибольшая общая подпоследовательность (НОП)
Наибольшая общая подпоследовательность (НОП)
Условие задачи
Даны две последовательности и . Требуется найти длину наибольшей общей подпоследовательности.
Наибольшая общая подпоследовательность (НОП)
Даны две последовательности и . Требуется найти длину наибольшей общей подпоследовательности.
Например, наибольшая общая подпоследовательность и является .
Обозначим как решение для префикса длины и префикса длины . Т.е. длину наибольшей общей подпоследовательности и .
Базовые случаи это:
Попытаемся теперь найти переходы для общего случая . Давайте разберем переходы:
Следовательно, имеем формулу:
Давайте для каждой не базовой состояний запомним наилучший переход. Т.е. мы знаем, что имеет три разных перехода:
Создадим другой массив и сохраним в какой переход наилучший для . Например, если то тогда имеем .
После этого теперь мы можем восстановить ответ. Инициализируем и делаем следующее до тех пор, пока и .
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = 0;
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
dp[i][j] = max(dp[i][j], dp[i][j - 1]);
if (a[i] == b[j]) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = -1;
if (dp[i - 1][j] > dp[i][j]) {
dp[i][j] = dp[i - 1][j];
p[i][j] = 1;
}
if (dp[i][j - 1] > dp[i][j]) {
dp[i][j] = dp[i][j - 1];
p[i][j] = 2;
}
if (a[i] == b[j] && dp[i - 1][j - 1] + 1 > dp[i][j]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
p[i][j] = 3;
}
}
}
vector<int> res;
int x = n, y = m;
while (x > 0 && y > 0) {
if (p[x][y] == 3) {
res.push_back(a[x]);
x -= 1;
y -= 1;
} else if (p[x][y] == 2) {
y -= 1;
} else { // p[x][y] == 1
x -= 1;
}
}
reverse(res.begin(), res.end());