侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-11-28 / 0 评论 / 0 点赞 / 162 阅读 / 1,274 字
温馨提示:
本文最后更新于 2023-02-22,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

897. 最长公共子序列


给定两个长度分别为 NNMM 的字符串 AABB ,求既是 AA 的子序列又是 BB 的子序列的字符串长度最长是多少。

输入格式

第一行包含两个整数 NNMM

第二行包含一个长度为 NN 的字符串,表示字符串 AA

第三行包含一个长度为 MM 的字符串,表示字符串 BB

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

输出格式

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

数据范围

1N,M10001 \le N,M \le 1000

输入样例:

4 5
acbd
abedc

输出样例:

3

解题

方法一:动态规划

思路

注意:以下分析均基于两字符串下标从 11 开始。

思维过程:

image-20230212185011161

如何去求集合划分出的四类(以下以 00,01,10,1100, 01, 10, 11 指代以上四类):

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

综上:

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

动态规划:

  • 状态定义:dp[i][j]dp[i][j] 表示字符串 AA 中前 ii 个字符与字符串 BB 中前 jj 个字符构成的公共子序列的最长长度。
  • 状态转移方程:dp[i][j]={max(dp[i1][j1]+1,max(dp[i1][j],dp[i][j1]))A[i]=B[j]max(dp[i1][j],dp[i][j1])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}
  • 初始状态:进行第一次状态转移前,所有位置的公共子序列的最大长度均为 11

代码

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;
}
0

评论区