最长公共子序列（线性dp）-java

当a[i]和b[j]都不取。即取字符串A前i 个字符和字符串B的前j个字符的最长公共子序列的长度dp[i-1]dp[j-1]
当a[i]不取，b[j]取。而dp[i-1][j]表示的是字符串A的前i-1个字符和字符串B的前j个字符的最长公共子序列，其中可能包括字符串B的第j个字符也可能不包括字符串B的第j个字符。
当a[i]取，b[j]不取。dp[i][j-1]表示的字符串A的前i个字符和字符串B的前j-1的字符的最长公共子序列，其中可能包括字符串A的第i个字符也可能不包括字符串A的第j个字符。
当a[i]和b[j]都取，即字符串A的第i个字符和字符串B的第j个字符相等时，那么就代表我们取字符串A的前i-1个字符和字符串B的前j-1个字符的最长公共子序列的长度（即dp[i-1][j-1]）加上1，既可以得到此时dp[i][j]的值，即 $dp[i][j] = dp[i-1]dp[j-1]+1$ 。

2. dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]的关系

图2.1dp[i-1][j]、dp[i][j-1]和dp[i-1][j-1]的关系

dp[i-1][j]表示字符串A的前i-1个字符和字符串B的前j个字符的最长公共子序列。

dp[i][j-1]表示的字符串A的前i个字符和字符串B的前j-1的字符的最长公共子序列

那么dp[i-1][j]和dp[i][j-1]的重复的部分就表示字符串A的前i-1个字符和字符串B的前j-1个字符串的最长公共子序列即dp[i-1][j-1]。（不取字符串A的第i个字符和字符串B的第j个字符）

3.dp数组的状态转移方程

因为我们dp[i][j]表示的值是上述所描述的4种情况取最大值，那么我们就不必再取dp[i-1][j-1]的值，因为dp[i-1][j]的值和dp[i][j-1]的值肯定都比dp[i-1][j-1]的值大，dp[i-1][j-1]分别是dp[i-1][j]和dp[i][j-1]的子集。

当a[i] != b[j]时:

$dp[i][j] = max(dp[i-1][j],dp[i][j-1])$

当a[i] = b[j]时：

$dp[i][j] = dp[i-1][j-1]+1$

4.dp数组具体如下

我们以测试样例字符串acbd和字符串abedc为例，dp数组各个值如下：

0 0 0 0 0 0 
0 1 1 1 1 1 
0 1 1 1 1 2 
0 1 2 2 2 2 
0 1 2 2 3 3

三、代码如下

1.代码如下（示例）：


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

public class 最长公共子序列 {
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static void main(String[] args) throws Exception{
        Scanner sc =new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int n = sc.nextInt();
        int m = sc.nextInt();
        String a = sc.next();
        String b = sc.next();
        char[] Achar = new char[1010];
        char[] Bchar = new char[1010];
        for(int i = 1;i <= n;i++){
            Achar[i] = a.charAt(i-1);
        }
        for(int i = 1;i <= m;i++){
            Bchar[i] = b.charAt(i-1);
        }
        int[][] dp = new int[1010][1010];
        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(Achar[i] == Bchar[j]){
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1]+1);
                }
            }
        }
        pw.println(dp[n][m]);
        pw.flush();
    }
    public static int nextInt()throws Exception{
        st.nextToken();
        return (int)st.nval;
    }
}

2.读入数据

4 5
acbd
abedc

3.代码运行结果

即acbd和abedc的最长公共子序列为abd，长度为3

总结

只要弄懂dp[i][j]、dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]各个值之间的关系和状态转移方程的由来即可解决最长公共子序列问题。

标签：java,dp,字符串,序列,线性,new,最长,个字符
From： https://blog.csdn.net/m0_63267251/article/details/137526076

最长公共子序列（线性dp）-java

文章目录

一、最长公共子序列

二、算法思路

1.dp[i][j]的四种情况