1. 最长公共子序列

1.1 题目

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 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.2 思路

属于动态规划之从左到右的尝试，由于题目涉及了2个序列，需要有2个指针来记录位置关系，其中i表示在text1上从0～i尝试的过程，j表示在text2上从0～j尝试的过程。

定义dp[i][j]，在经过在text1和text2上尝试后，在text1的0～i，text2的0～j的范围上最长的子序列长度为dp[i][j]
寻找dp[i][j]和前面的关系，是和i-1直接的关系，还是j-1直接关系，还是需要重新遍历比较的关系，本题的关系为：
1. 如果text1[i]==text2[j], 最长子序列长度+1，dp[i][j]=dp[i-1][j-1]+1
2. text1[i]!=text2[j],那么dp[i][j]取以下2种情况的Max
  1. 取text1上0~i 和 text2上0~j-1的最长子序列长度
  2. 取text1上0~i-1 和 text2上0~j的最长子序列长度
边界：
1. dp[0][j] 比较text1[0]和text2[j]，如果相等为1，不相等为0
2. 同理，dp[i][0] 比较text1[i]和text2[0]，如果相等为1，不相等为0
结果：dp[text1.length-1][text2.length-1]

1.3 代码

 public int longestCommonSubsequence(String text1, String text2) {
        if(text1 == null || text1.length() == 0|| text2 == null || text2.length() == 0){
            return 0;
        }
        int[][] dp = new int[text1.length()][text2.length()];
        int flag = 0;
        for(int i=0; i< text1.length();i++){
            if(text1.charAt(i) == text2.charAt(0)){
                flag = 1;   
            }
            dp[i][0] = flag;
        }
        flag = 0;
        for(int j=0; j< text2.length();j++){
            if(text1.charAt(0) == text2.charAt(j)){
                flag = 1;   
            }
            dp[0][j] = flag;
        }

        for(int i=1; i< text1.length();i++){
             for(int j=1; j< text2.length();j++){
                if(text1.charAt(i) == text2.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]);
                }
             }
        }
        return dp[text1.length()-1][text2.length()-1];
    }

2. 不同的子序列

2.1 题目

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

示例 1：

输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabb b it
rab b bit
ra b bbit

示例 2：

输入：s = "babfbaf", t = "baf"
输出：5
解释：
如下图所示, 有 5 种可以从 s 中得到 "baf" 的方案。
ba b f baf
ba b fba f
b abfb af
ba bfb af
babf baf

2.2 思路

属于动态规划之从左到右的尝试，由于题目涉及了2个序列，需要有2个指针来记录位置关系，其中i表示在s上从0～i尝试的过程，j表示在t上从0～j尝试的过程。
题意：s的长度必然是大于等于t的，不然就直接返回0

定义dp[i][j]，在经过在s和t上尝试后，在s的0～i，t的0～j的范围上，t[0~j]在s[0~i]上出现的次数 = dp[i][j]
在本题中dp[i][j]和dp之间位置的关系是：
1. 如果s[i]=t[j],那么相当于在s[0~i-1]和t[0~j-1]上加了个一个相同的后缀，那自然就是dp[i][j]=dp[i-1][j-1]+1
2. 如果s[i]！=t[j]，分2种情况
  1. 看t[0~j]在s[0~i-1]上出现的次数，也是符合要求的需要记录下来
  2. 同时符合要求的，看t[0~i-1]在s[0~j]上出现的次数（虽然此时s[i]！=t[j]，但是如果下一个位置相同了的话，那就相当于在此基础上加1就可以，所以也必须要记录下来）
边界:
1. dp[i][0] 比较s[i]和t[0]，如果相等累加1，代表t[0]出现的次数累计
2. dp[1][j] 直接为0（题意：s的长度必然是大于等于t的，不然就直接返回0）
返回：dp[s.length()-1][t.length()-1];

2.3 代码

    public int numDistinct(String s, String t) {
            if(s == null || t == null){
            return 0;
        }
        if(s.length() < t.length()){
            return 0;
        }
        int[][] dp = new int[s.length()][t.length()];
        int flag = 0;
         for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == t.charAt(0)){
                flag++;
            }
            dp[i][0] = flag;
         }
        flag = 0;
        for (int j = 1; j < t.length(); j++) {
            dp[0][j] = 0;
        }
        for (int i = 1; i < s.length(); i++) {
            for (int j = 1; j < t.length(); j++) {
                if(s.charAt(i) != t.charAt(j)){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                }
            }
        }
        return dp[s.length()-1][t.length()-1];
    }

子序列相关2