侧边栏壁纸
博主头像
GabrielxD

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

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-11-28 / 0 评论 / 0 点赞 / 32 阅读 / 615 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-11-28,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

897. 最长公共子序列


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

输入格式

第一行包含两个整数 NNMM

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

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

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

输出格式

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

数据范围

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

输入样例:

4 5
acbd
abedc

输出样例:

3

解题

方法一:动态规划

思路

思维过程:

image-20221128161219940

动态规划:

  • 状态定义:dp[i][j]dp[i][j] 表示字符串 AA 中前 ii 个字符与字符串 BB 中前 jj 个字符构成的公共子序列的最长长度。
  • 状态转移方程:dp[i][j]={dp[i1][j1]+1A[i]=B[j]max(dp[i1][j],dp[i][j1])A[i]B[j]dp[i][j] = \begin{cases} dp[i - 1][j - 1] + 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 = br.readLine().toCharArray();
        char[] b = 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 - 1] == b[j - 1]) {
                    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

评论区