Eng uzun umumiy ostketma-ketlik (LCS) va eng uzun ortib boruvchi ostketma-ketlik (LIS) - Resources

Bosh sahifa Kurslar Resurslar Masalalar Milliy olimpiada Musobaqalar Reyting

...

Bosh sahifa/Resources/Dynamic Programming/Eng uzun umumiy ostketma-ketlik (LCS) va eng uzun ortib boruvchi ostketma-ketlik (LIS)

Eng uzun umumiy ostketma-ketlik (LCS) va eng uzun ortib boruvchi ostketma-ketlik (LIS)

Longest Common Subsequence (LCS) Problem Statement

Given two sequences $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_m$ , we need to find the length of their .

b_{1}, b_{2}, \dots, b_{m}

longest common subsequence

For example, for the sequences $[1, 2, 3]$ and $[2, 3, 1]$ , one longest common subsequence is $[2, 3]$ .

Solution

Let dp(i, j) denote the answer for:

the prefix of a of length i;
the prefix of b of length j.

In other words, dp(i, j) is the length of the longest common subsequence of

a[1 \ldots i]

and

b[1 \ldots j]

Base Cases

If one of the prefixes is empty, then the answer is 0:

dp(0, j) = 0 \quad (0 \leq j \leq m)

dp(i, 0) = 0 \quad (0 \leq i \leq n)

Transition

Now consider the general case $dp(i, j)$ , where $i > 0$ and $j > 0$ .

There are three possibilities:

a[i] is not used in the answer, so we transition from dp(i - 1, j);
b[j] is not used in the answer, so we transition from dp(i, j - 1);
both a[i] and b[j] are used in the answer. This is possible only if a[i] == b[j], and then we transition from dp(i - 1, j - 1) + 1.

So the recurrence is:

dp(i, j) = \max \begin{cases} dp(i - 1, j), \\ dp(i, j - 1), \\ dp(i - 1, j - 1) + 1, & \text{if } a_i = b_j \end{cases}

LCS with Reconstruction

To restore one actual longest common subsequence, we can remember which transition was best for each state.

Let p(i, j) store the transition used to get dp(i, j):

1 means we came from dp(i - 1, j);
2 means we came from dp(i, j - 1);
3 means we came from dp(i - 1, j - 1) + 1.

Then we start from (n, m) and move backward until one of the indices becomes zero.

If p(x, y) == 3, then a[x] belongs to the answer, so we add it and move to (x - 1, y - 1);
If p(x, y) == 2, we move to (x, y - 1);
If p(x, y) == 1, we move to (x - 1, y).

Longest Increasing Subsequence (LIS) Problem Statement

Given a sequence

a_1, a_2, \ldots, a_n

we need to find its longest increasing subsequence.

For example, for the sequence

[2, 4, 1, 4, 2, 3, 6, 10]

one longest increasing subsequence is

[1, 2, 3, 6, 10]

Solution

Solution 1

One possible idea is to create a sorted copy of the sequence and compute the LCS between the original sequence and the sorted one.

This idea is useful conceptually, but in practice it is not the standard way to solve LIS.

Solution 2

Let dp(i) denote the length of the longest increasing subsequence in the prefix

a[1 \ldots i]

under the condition that a[i] is included in the subsequence.

So a[i] must be the last element of the subsequence counted by dp(i).

Base Case

If the subsequence contains only a[i], then:

dp(i) = 1

Transition

To compute dp(i), we try all earlier positions j < i such that

a_j < a_i

If we place a[i] after a[j], then we get:

dp(i) = dp(j) + 1

So the recurrence is:

dp(i) = \max \begin{cases} 1, \\ dp(j) + 1 & \text{for all } j < i \text{ such that } a_j < a_i \end{cases}

The final answer is:

\max_{1 \leq i \leq n} dp(i)

LIS with Reconstruction

To restore one actual LIS, we store the best previous position for each i.

Let p(i) mean:

0, if the subsequence ending at i consists only of a[i];
j, if the best transition is from position j.

Then after computing dp, we find the position x where dp[x] is maximum, and follow the parent pointers backward.

i

=

bj

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());