Violent recursion to dynamic programming 06 (the sword refers to Offer II 095. Longest common subsequence)

1143.最长公共子序列

力扣题目链接

给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列的长度.

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串.

例如,“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列.两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列.

若这两个字符串没有公共子序列,则返回 0.

示例 1:

输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace”,它的长度为 3.

示例 2:
输入：text1 = “abc”, text2 = “abc”
输出：3
解释：最长公共子序列是 “abc”,它的长度为 3.

示例 3:
输入：text1 = “abc”, text2 = “def”
输出：0
解释：两个字符串没有公共子序列,返回 0.

提示:

• 1 <= text1.length <= 1000
• 1 <= text2.length <= 1000
  输入的字符串只含有小写英文字符.

暴力递归

I can't tell,Whoever said it, please say it in the comment area.

  public int longestCommonSubsequence(String text1, String text2) {
    
        return getLongLest(text1, text1.length() - 1, text2, text2.length() - 1);
    }


    private int getLongLest(String text1, int text1Index, String text2Str, int text2tIndex) {
    
        if (text1Index == 0 && text2tIndex == 0) {
    
            //Compares the current bits for equality
            return text1.charAt(text1Index) == text2Str.charAt(text2tIndex) ? 1 : 0;
        } else if (text1Index == 0) {
    
            //When the left ends, the left does not move more than the right
            return text1.charAt(text1Index) == text2Str.charAt(text2tIndex) ? 1 : getLongLest(text1, text1Index, text2Str, text2tIndex - 1);
        } else if (text2tIndex == 0) {
    
            //When the right side ends, the right side does not move more than the left side
            return text1.charAt(text1Index) == text2Str.charAt(text2tIndex) ? 1 : getLongLest(text1, text1Index - 1, text2Str, text2tIndex);
        } else {
    
            //都不為0
            int p1 = getLongLest(text1, text1Index, text2Str, text2tIndex - 1);
            int p2 = getLongLest(text1, text1Index - 1, text2Str, text2tIndex);
            //No end is more than the middle
            int p3 = text1.charAt(text1Index) == text2Str.charAt(text2tIndex) ? 1 + getLongLest(text1, text1Index - 1, text2Str, text2tIndex - 1) : Integer.MIN_VALUE;
            return Math.max(p1, Math.max(p2, p3));
        }
    }

动态规划

This is much better to say
Initialize the first bit first,相等则为1,否则为0,初始化第一行,用aCompare with each one,相等则为1,Otherwise, the previous number,Why for the previous number？Think for yourself,比如a和a比是1,那a和ab比呢,也是1啊.纵向也一样;
然后从ij1开始比,Because the two are compared to each other,If the current bits are not equal,Take the maximum value from the left and the top,If the current bits are equal,Also and top left + 1 Take the maximum value.That is, the current position is moved one position backward,Naturally use the number at that position + 1 了.

 public int longestCommonSubsequence2(String text1, String text2) {
    
        int m = text1.length();
        int n = text2.length();
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();
        int[][] dp = new int[m][n];
        //first initialization
        dp[0][0] = s1[0] == s2[0] ? 1 : 0;
        //Row and column initialization
        for (int i = 1; i < m; i++) {
    
            dp[i][0] = s1[i] == s2[0] ? 1 : dp[i - 1][0];
        }
        for (int i = 1; i < n; i++) {
    
            dp[0][i] = s1[0] == s2[i] ? 1 : dp[0][i - 1];
        }
        for (int i = 1; i < m; i++) {
    
            for (int j = 1; j < n; j++) {
    
                int left = dp[i][j - 1];
                int up = dp[i - 1][j];
                int cur = s1[i] == s2[j] ? 1 + dp[i - 1][j - 1] : 0;
                dp[i][j] = Math.max(left, Math.max(up, cur));
            }
        }
        return dp[m - 1][n - 1];
    }