算法训练营Day55(子序列--编辑距离）

这道题目算是?编辑距离问题?的入门题目（毕竟这里只是涉及到减法），慢慢的，后面就要来解决真正的编辑距离问题了

和最长公共子序列相似

他那道题区别就是else里面，两个都可以删，就是取max（i j-1? i-1 j）

class Solution {
    public boolean isSubsequence(String s, String t) {
        int len1 = s.length();
        int len2 = t.length();
        //以 i-1 j-1为结尾的，字符串s 与t公共子序列的长度
        int [][] dp = new int[len1+1][len2+1];

        for(int i =1;i<=len1;i++){
            for(int j = 1;j<=len2;j++){
                if(s.charAt(i-1) == t.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{//看这里就能想明白为什么j-1
                    //  a b c
                    //a 1 0 0 
                    //h 1 0 0
                    //b 1 2 0
                    dp[i][j] = dp[i][j-1];
                } 
            }
        }
       
        return len1==dp[len1][len2];
    }
}

?115.不同的子序列??

115. 不同的子序列 - 力扣（LeetCode）

好懵，二刷好好再看下

class Solution {
    public int numDistinct(String s, String t) {
        int len1 = s.length();
        int len2 = t.length();
        //以i-1为结尾的s中有多少个以j-1为结尾的t的个数
        int [][] dp= new int[len1+1][len2+1];
        for(int i = 0;i<len1;i++){
            dp[i][0] = 1;
        }
        for(int i = 1;i<=len1;i++){
            for(int j = 1;j<=len2;j++){
                
                if(s.charAt(i-1)==t.charAt(j-1)){
                    //相同的话，就是上一个的个数,  不考虑i-1可能也符合，那么就是i-1 j
                    dp[i][j] = dp[i-1][j-1]+ dp[i-1][j] ;//bagg bag
                }else{
                    //不同，就是不考虑i，模拟删除这个元素拥有的个数
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[len1][len2];
    }
}