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