【动态规划】代码随想录算法训练营第五十四天 |392.判断子序列， 115.不同的子序列（待补充）

ゝ一纸荒年。 2024-04-23 04:39 8阅读 0赞

## 392.判断子序列 ##

1、题目链接：[. - 力扣（LeetCode）][. - _LeetCode]

2、文章讲解：[代码随想录][Link 1]

3、题目：

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

示例 1：

*  输入：s = "abc", t = "ahbgdc"
 *  输出：true

示例 2：

*  输入：s = "axc", t = "ahbgdc"
 *  输出：false

提示：

*  0 <= s.length <= 100
 *  0 <= t.length <= 10^4

两个字符串都只由小写字符组成。

4、视频链接：

[动态规划，用相似思路解决复杂问题 | LeetCode：392.判断子序列\_哔哩哔哩\_bilibili][_ LeetCode_392._bilibili]

class Solution {
        public boolean isSubsequence(String s, String t) {
            int length1 = s.length();
            int length2 = t.length();
            int[][] dp = new int[length1 + 1][length2 + 1];
            for (int i = 1; i <= length1; i++) {
                for (int j = 1; j <= length2; j++) {
                    if (s.charAt(i - 1) == t.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else {
                        dp[i][j] = dp[i][j - 1];
                    }
                }
            }
            if (dp[length1][length2] == length1) {
                return true;
            } else {
                return false;
            }
        }
    }

## 115.不同的子序列 ##

1、题目链接：[. - 力扣（LeetCode）][. - _LeetCode 1]

2、文章讲解：[代码随想录][Link 2]

3、题目：

我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。

现在，我们可以绘制一些连接两个数字 A\[i\] 和 B\[j\] 的直线，只要 A\[i\] == B\[j\]，且我们绘制的直线不与任何其他连线（非水平线）相交。

以这种方法绘制线条，并返回我们可以绘制的最大连线数。

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

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

![b12d0d6c63b3f84224c6fed7265e8929.jpeg][]

提示：

*  0 <= s.length, t.length <= 1000
 *  s 和 t 由英文字母组成

4、视频链接：

[动态规划之子序列，为了编辑距离做铺垫 | LeetCode：115.不同的子序列\_哔哩哔哩\_bilibili][_ LeetCode_115._bilibili]

class Solution {
        public int numDistinct(String s, String t) {
            int[][] dp = new int[s.length() + 1][t.length() + 1];
            for (int i = 0; i < s.length() + 1; i++) {
                dp[i][0] = 1;
            }
    
            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()];
        }
    }

[. - _LeetCode]: https://leetcode.cn/problems/is-subsequence/
[Link 1]: https://programmercarl.com/0392.%E5%88%A4%E6%96%AD%E5%AD%90%E5%BA%8F%E5%88%97.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[_ LeetCode_392._bilibili]: https://www.bilibili.com/video/BV1tv4y1B7ym/
[. - _LeetCode 1]: https://leetcode.cn/problems/distinct-subsequences/
[Link 2]: https://programmercarl.com/0115.%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[b12d0d6c63b3f84224c6fed7265e8929.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/6ebfa00defe541e88fd2879b23adfb03.jpeg
[_ LeetCode_115._bilibili]: https://www.bilibili.com/video/BV1fG4y1m75Q/