#yyds干货盘点# 动态规划专题：最长公共子序列(一)

1.简述：

给定两个字符串 s1 和 s2，长度为 n 和 m  。求两个字符串最长公共子序列的长度。

所谓子序列，指一个字符串删掉部分字符（也可以不删）形成的字符串。例如：字符串 "arcaea" 的子序列有 "ara" 、 "rcaa" 等。但 "car" 、 "aaae" 则不是它的子序列。

所谓 s1 和 s2 的最长公共子序列，即一个最长的字符串，它既是 s1 的子序列，也是 s2 的子序列。

数据范围 :  。保证字符串中的字符只有小写字母。

要求：空间复杂度 ，时间复杂度 

进阶：空间复杂度 ，时间复杂度 

第一行输入一个整数 n 和 m ，表示字符串 s1 和 s2 的长度。

接下来第二行和第三行分别输入一个字符串 s1 和 s2。

输出两个字符串的最长公共子序列的长度

输入：

5 6
abcde
bdcaaa

输出：

2

说明：

最长公共子序列为 "bc" 或 "bd" ，长度为2

输入：

3 3
abc
xyz

输出：

0

2.代码实现：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String nums = scanner.nextLine();
        String s1 = scanner.nextLine();
        String s2 = scanner.nextLine();
        // 开始算法
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        int[][] dp = new int[c1.length+1][c2.length+1];
        for (int i = 1; i <= c1.length; i++) {
            for (int j = 1; j <= c2.length; j++) {
                if (c1[i-1] == c2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        System.out.println(dp[c1.length][c2.length]);
    }
}