绞尽脑汁无法爆破。题解2129: 最长公共子序列 （动态规划）

解题思路: 动态规划看的懂，不会写，终究还是练少了。直接copy。

注意事项: 力扣-最长公共子序列解析

                B站-某最长公共子序列解析

参考代码:

import java.util.Scanner;

/**
 * @author fzy
 * @create 2021/10/10 11:02
 **/
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();

        int n=str1.length();//第一个子串长度 (二维 行数)
        int m=str2.length();//第二个子串长度 (二维 列数)

        int[][] dp = new int[n + 1][m + 1];

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                    //两个字符串的最后一位相等，那么问题就转化成了
                    //字符串str1的[1,j-1]区间和字符串str1的[1,j-1]区间的最长公共子序列长度再加上1
                    //即dp[i][j] = dp[i - 1][j - 1] + 1
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i- 1][j - 1] + 1;
                } else {
                    //若str[i] != str[j]，也就是说两个字符串的最后一位不相等，
                    //那么字符串str1的[1,i]区间和字符串str2的[1,j]区间的最长公共子序列长度无法延长，
                    //因此f[i][j]就会继承dp[i-1][j]与dp[i][j-1]中的较大值，
                    //即dp[i][j] = max(dp[i - 1][j],dp[i][j - 1])
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        System.out.println(dp[n][m]);
    }
}