Module 1: 2D DP

Longest common subsequence (LCS)
Longest Increasing Subsequence (LIS)
Longest Increasing Subsequence (LIS) in $O(N \log N)$
Knapsack problem
Lazy DP

Module 2: DSU

System of disjoint sets

Module 3: MST

Minimum and maximum spanning trees
Kruskal's Algorithm
Prim's Algorithm
Borůvka's Algorithm

Module 4: Combinatorics

Stars and columns
The principle of inclusion-exclusion

Module 5: Geometry

Finding the area of a simple polygon

Module 6: Arbitrary-Precision Arithmetic

Long Arithmetic

Module 7: Data structures for keeping minimum

Stack with Minimum
Queue with Minimum
Deque with Minimum

Module 8: Heap [BONUS]

Binary Heap

Longest common subsequence (LCS) - Preparation to IOI Part 3

Home Courses Resources Problems National Olympiad Contests Leaderboard

...

Home/Courses/Preparation to IOI Part 3/Module 1: 2D DP/Longest common subsequence (LCS)

Longest common subsequence (LCS)

Longest Common Subsequence (LCS)

Problem statement

Two sequences $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_m$ are given. It is required to find the length of the longest common subsequence.

Up next

Longest Increasing Subsequence (LIS)

Longest increasing subsequence (LIS)

b1,b2,…,bm

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

Solution

Let $dp(i, j)$ denote the solution for the prefix of $a$ of length $i$ and the prefix of $b$ of length $j$ . I.e., the length of the longest common subsequence of $a[1 \ldots i]$ and $b[1 \ldots j]$ .

The base cases are:

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

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

Now let us try to find transitions for the general case $dp(i, j) \ (0 < i \leq n, \ 0 < j \leq m)$ . Let us analyze the transitions:

Element $a_i$ is not included in the common subsequence. Then we have the transition $dp(i - 1, j)$ .
Element $b_j$ is not included in the common subsequence. Then we have the transition $dp(i, j - 1)$ .
Elements $a_i$ and $b_j$ are included in the common subsequence. This is possible only if they are equal, i.e., $a_i=b_j$ . Then we have the transition .

Therefore, we have the formula:

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

LCS with reconstruction

Let us, for each non-base state, remember the best transition. I.e., we know that $dp(i, j)$ has three different transitions:

$dp(i - 1, j)$
$dp(i, j - 1)$
$dp(i - 1, j - 1) + 1)$

Let us create another array $p(i, j)$ and store in $p(i, j)$ which transition is best for $d(i, j)$ . For example, if $dp(i, j) = dp(i - 1, j - 1) + 1$ then we have $p(i, j) = 3$ .

After that, we can now reconstruct the answer. Initialize $x=n, y=m$ and do the following until $x>0$ and $y>0$ .

If $p(x, y) == 3$ then we included $a_x$ and $b_y$ in the common subsequence. Therefore, add $a_x$ to the answer and move to $:x=x-1, y:=y-1$ .
If $p(x, y) == 2$ then move to $x,y:=y-1$ .
If $p(x, y) == 1$ then move to $x:=x-1,y$ .

bj

dp(i - 1, j - 1) + 1

=

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