线性dp

先行dp题目： 牛客dp专题 AcWing线性dp专题

import java.util.Scanner;

/**
 * 最长公共子序列
 *
 * 给定两个字符串 s1 和 s2，长度为 n 和 m  。求两个字符串最长公共子序列的长度。
 * 所谓子序列，指一个字符串删掉部分字符（也可以不删）形成的字符串。
 * 例如：字符串 "arcaea" 的子序列有 "ara" 、 "rcaa" 等。但 "car" 、 "aaae" 则不是它的子序列。
 * 所谓 s1 和 s2 的最长公共子序列，即一个最长的字符串，它既是 s1 的子序列，也是 s2 的子序列。
 * 数据范围 : 1<= m,n<=1000 1≤m,n≤1000 。保证字符串中的字符只有小写字母。
 *
 * 5 6
 * abcde
 * bdcaaa
 *
 * 2
 */
public class 线性dp {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        String s1=sc.next();
        String s2=sc.next();
        //定义dp数组，dp[i][j]表示s1的前i+1个字符和s2的前j+1个字符可以匹配的最多的子序列的个数
        int[][] dp=new int[n][m];
        dp[0][0]=s1.charAt(0)==s2.charAt(0)?1:0;
        //初始化边界值
        for(int i=1;i<n;i++){
            if(dp[i-1][0]==1){
                dp[i][0]=1;
            }else{
                dp[i][0]=s1.charAt(i)==s2.charAt(0)?1:0;
            }
        }
        //初始化边界值
        for(int j=1;j<m;j++){
            if(dp[0][j-1]==1){
                dp[0][j]=1;
            }else{
                dp[0][j]=s1.charAt(0)==s2.charAt(j)?1:0;
            }
        }
        //dp状态转移，状态转移方程考虑相等和不想等两种情况
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                if(s1.charAt(i)==s2.charAt(j)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        System.out.println(dp[n-1][m-1]);
    }
}