【动态规划, LCS】最长公共子序列

题目

897. 最长公共子序列

---

给定两个长度分别为 $N$ 和 $M$ 的字符串 $A$ 和 $B$ ，求既是 $A$ 的子序列又是 $B$ 的子序列的字符串长度最长是多少。

输入格式

第一行包含两个整数 $N$ 和 $M$ 。

第二行包含一个长度为 $N$ 的字符串，表示字符串 $A$ 。

第三行包含一个长度为 $M$ 的字符串，表示字符串 $B$ 。

字符串均由小写字母构成。

输出格式

输出一个整数，表示最大长度。

数据范围

$1 \le N,M \le 1000$

输入样例：

4 5
acbd
abedc

输出样例：

3

解题

方法一：动态规划

思路

注意：以下分析均基于两字符串下标从 $1$ 开始。

思维过程：

如何去求集合划分出的四类（以下以 $00, 01, 10, 11$ 指代以上四类）：

• $00$ ：显然地，根据状态表示，这一类的最大值为：$f(i - 1, j - 1)$ 。
• $01$ ：类似地，这一类的最大值表示为：$f(i - 1, j)$ ，吗？
  并不是这样，确切来说，该类表示的集合是 $f(i-1, j)$ 表示的集合的子集，因为：根据状态定义， $f(i - 1, j)$ 表示所有从 $A[1 \dots i - 1]$ 与 $B[1 \dots j]$ 中选出的公共子序列，注意：此时 $B[j]$ 并不是被必选的，而 $"01"$ 这一类的集合要求是必定包含 $B[j]$ ，所以上面说它是子集。
  但是，用 $f(i - 1, j)$ 来只带这一类的最大值是可行的，因为我们只需要保证集合划分得不重不漏，而求最大值时是可以重复的。
  
• $10$ ：该类表示的集合是 $f(i, j - 1)$ 表示的集合的子集，理由同上。
• $11$ ：由于 $A[i]$ 是 $A[1\dots i]$ 中最后一个字符， $B[j]$ 也是 $B[1 \dots j]$ 中最后一个字符，所以若想让公共子序列中同时包含 $A[i]$ 和 $B[j]$ 就必须让 $A[i] = B[j]$ ，此时这一类的最大值恰好是 $f(i - 1, j - 1) + 1$ 。

综上：

• $\max(00, 01, 10) = \max(f(i-1, j), f(i, j-1))$
• $\max(11) = f(i-1, j-1) + 1$

动态规划：

• 状态定义：$dp[i][j]$ 表示字符串 $A$ 中前 $i$ 个字符与字符串 $B$ 中前 $j$ 个字符构成的公共子序列的最长长度。
• 状态转移方程：$dp[i][j] = \begin{cases} \max(dp[i - 1][j - 1] + 1, \max(dp[i - 1][j], dp[i][j - 1])) & A[i] = B[j]\\ \max(dp[i - 1][j], dp[i][j - 1]) & A[i] \neq B[j] \end{cases}$ 。
• 初始状态：进行第一次状态转移前，所有位置的公共子序列的最大长度均为 $1$ 。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        char[] a = ('\0' + br.readLine()).toCharArray();
        char[] b = ('\0' + br.readLine()).toCharArray();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                if (a[i] == b[j]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
                }
            }
        }
        System.out.println(dp[n][m]);
    }
}

#include <iostream>

using namespace std;

const int N = 1010;
int n, m;
char a[N], b[N];
int dp[N][N];

int main() {
    scanf("%d%d\n%s\n%s", &n, &m, a + 1, b + 1);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            if (a[i] == b[j]) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
        }
    }
    printf("%d\n", dp[n][m]);
    
    return 0;
}