Day46 力扣动态规划 : 392.判断子序列 ｜ 115.不同的子序列

392.判断子序列

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

https://programmercarl.com/0392.%E5%88%A4%E6%96%AD%E5%AD%90%E5%BA%8F%E5%88%97.html

第一印象

我直接按逻辑去写

class Solution {
    public boolean isSubsequence(String s, String t) {
        int cur = 0;
        int flag = 0;

        loop:
        for (int i = 0; i < s.length(); i++) {
            for (int j = cur; j < t.length(); j++) {
                if (s.charAt(i) == t.charAt(j)) {
                    //下一次从t串的 j + 1开始找，因为j是这次找到的。
                    cur = j + 1;
                    continue loop;
                } else {
                    cur = j + 1;
                }
            }
            if (cur >= t.length()) return false;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

直接a了

但是一点也不dp，我直接看题解学习了。

看完题解的思路

判断s是不是t的子序列，其实就是判断两个字符串的公共子序列长度是不是s的长度。

那这道题本质就是最长公共子序列。

dp数组含义：dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。

实现中的困难

没有

感悟

感觉我做这个最长公共子序列，有一点背答案了

代码

class Solution {
    public boolean isSubsequence(String s, String t) {
        //dp
        int[][] dp = new int[t.length() + 1][s.length() + 1];
        int result = 0;
        //init

        //func
        for (int i = 1; i < s.length() + 1; i++) {
            for (int j = 1; j < t.length() + 1; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[j][i] = dp[j - 1][i - 1] + 1;
                    result = dp[j][i];
                } else {
                    dp[j][i] = Math.max(dp[j - 1][i], dp[j][i - 1]);
                }
            }
        }
        return result == s.length() ? true : false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

115.不同的子序列

但相对于刚讲过 392.判断子序列，本题 就有难度了 ，感受一下本题和 392.判断子序列 的区别。

https://programmercarl.com/0115.%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97.html

第一印象

直接看题解！

看完题解的思路

这两道题给我弄的有点晕啊

• 我没明白这个和 编辑距离 四个字有什么关系。
• 以及模拟删除 s串的元素 是什么意思。

这么说最长公共子序列那道题，max（dp[i-1][j], dp[i][j-1]) 就是模拟删除 s和删除 t两种？

到底是什么模拟删除？

dp数组

这个部分还是和前两道题一样的

dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。

递推公式

主要分两种情况考虑

• s[i - 1] 与 t[j - 1]相等
• s[i - 1] 与 t[j - 1] 不相等

当s[i - 1] 与 t[j - 1]相等时，dp[i][j] 有两部分组成，一个是用 s[i-1] 来匹配 t[j-1] , 那么这个个数就是dp[i-1][j-1]。

还有一部分是不用s[i-1] 来匹配。其实到这里我也挺懵逼，怎么都相同还不用s[i-1]来匹配。

例如： s：bagg 和 t：bag

我们遍历s[3] 时，是第二个g。如果用它来匹配t[2] 的g，这种情况s包含t的个数就是bag包含ba的个数. dp[i-1][j-1]

如果不用它来匹配t[2]的g，这种情况s包含t的个数就是bag包含bag的个数。就是模拟删除这个 s[3] 。dp[i-1][j]

所以dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

哎卧槽有点混乱了。

第二个是s[i - 1] 与 t[j - 1] 不相等的时候。dp[i][j]只有一部分组成，不用s[i - 1]来匹配（就是模拟在s中删除这个元素），即：dp[i][j] = dp[i - 1][j]

初始化

s 是行 遍历 i

t 是列 遍历 j

dp[0][j] 代表 s是空的，s里面有多少个t，那肯定0个。
dp[i][0] 代表 t是空的，s里面有多少个t，那有一个。
dp[0][]0] 代表s和t都是空的，s里面有多少个t，也是有一个。

比如 s = bagg , t = bag

最开始，两个元素就相同了。

那么这个时候的 dp[1][1] = 1 才对。

dp[1][1] = dp[0][0] + dp[0][1] = 1 + 0.

合理的

遍历顺序

看得出直接正序了

实现中的苦难

最后返回的是dp[s.length][t.length]

这道题又是会更新到最后的了，不是中间某个数可能最大了。

因为一定要找尽 s 串，s 串的最后元素代表的一定是最大的。

而之前的题，？？？？？？？？？？

哎卧槽晕了

感悟 好难啊

我觉得这道题好难。

• 什么是模拟删除元素？

我觉得有必要画图模拟一下了。

画了，但还是没想明白。

或者可以这么想，比如s串遍历到了 ra， t这个时候是rab

a和b不相等

那么 ra 中有rab的个数就是 r 中 有 rab 的个数。这个就是模拟删除 s 中的元素。 那么为什么不模拟 删除 t 中的元素呢？

就是卡哥说的因为是找 s 中有多少个 t ，再结合 dp 数组的含义。s 到i-1 和 t 到j-1 了时，s中有多少个t。所以自然不用看删除 t 的话 ra中有多少个 ra（s的）

再举个例子
如果s遍历到了rab，t这个时候也是rab

b 和 b 相等

那么rab中有rab的个数就是 ra 中有ra的个数 + ra 中有rab的个数。

为什么要加上ra中有rab的个数呢？因为这里加的就是重复的情况。

比如 s遍历到rabb，t这个时候是rab。

因为b和b相等。那么rabb中有rab的个数就是 rab中有 ra的个数 + rab中有rab的个数。

哎目前我就通过这三个例子去理解，差不多吧，以后再悟。

反正就是通过这样的递推公式，在 i 循环的过程中，就能求出每个情况 s 里有多少个t。

然后 s 遍历完了，也就求出来 整个 s有多少个t了。

所以最后返回的也是 dp 数组的最后元素。

代码

class Solution {
    public int numDistinct(String s, String t) {
        //dp
        int[][] dp = new int [s.length() + 1][t.length() + 1];
        
        //init
        for (int i = 0; i < s.length() + 1; i++) {
            dp[i][0] = 1;
        }

        //func
        for (int i = 1; i < s.length() + 1; i++) {
            for (int j = 1; j < t.length() + 1; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[s.length()][t.length()];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23