// 两个字符串的最大公共子序列长度
// LCS(m,n)表示：字符串s1[0~m]，和字符串s2[0~n]的最长公共子序列；
// 递归公式&&状态转移
// 两种情况：
// 1、s1[m] == s2[n],LCS(m,n) = 1+LCS(m-1,n-1);
// 2、s1[m] != s2[n],LCS(m,n) = max(LCS(m-1,n),LCS(m,n-1));

public static int LCS(String s1, String s2) {

    int len1 = s1.length();
    int len2 = s2.length();

    int res = 0;

    if (len1 == 0 || len2 == 0) {//递归出口，基本情况，有一个序列空，则返回0
        return 0;
    }

    //自顶向下分析，两个序列的最后元素是否相同

    if (s1.charAt(s1.length() - 1) == s2.charAt(s2.length() - 1)) {
        res = 1 + LCS(s1.substring(0, s1.length() - 1), s2.substring(0, s2.length() - 1));
    } else {
        int a = LCS(s1.substring(0, s1.length() - 1), s2);
        int b = LCS(s1, s2.substring(0, s2.length() - 1));
        res = Math.max(a, b);
    }
    return res;
}

public static int LCS_DP(String s1, String s2) {

    int m = s1.length();
    int n = s2.length();

    // 1、开数组,和序列有关，因此多开一个位置;从1开始读取，因为会用到i-1
    int[][] dp = new int[m + 1][n + 1];
    // dp[i][j] 代表：当考虑x串的第i个位置，y串的第j个位置时，我们最长公共子串的长度。还有一点需注意：此处的i始终在x串上滑动，j 始终在y串滑动

    // 2、初始化dp；当摸一个序列是没有元素是，则LCS是0；
    for (int i = 0; i <= m; i++) {
        dp[i][0] = 0;
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = 0;
    }

    // 3、状态转移，更新dp
    for (int i = 1; i <= m; i++) {// 要从1开始读取，因为会用到i-1
        for (int j = 1; j <= n; j++) {

            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

    }

    return dp[m][n];
}