题目描述
这是 LeetCode 上的 115. 不同的子序列 ，难度为 困难。
Tag : 「线性 DP」
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
题目数据保证答案符合 32 位带符号整数范围。
示例 1：
输入：s = "rabbbit", t = "rabbit" 输出：3 解释： 如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。 (上箭头符号 ^ 表示选取的字母) rabbbit ^^^^ ^^ rabbbit ^^ ^^^^ rabbbit ^^^ ^^^ 复制代码
示例 2：
输入：s = "babgbag", t = "bag" 输出：5 解释： 如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。 (上箭头符号 ^ 表示选取的字母) babgbag ^^ ^ babgbag ^^ ^ babgbag ^ ^^ babgbag ^ ^^ babgbag ^^^ 复制代码
提示：
- 0 <= s.length, t.length <= 1000
- s 和 t 由英文字母组成
基本思路
有两个字符串 s 和 t，长度数量级都为 10^3103。
一个朴素的想法是，找出所有 s 的子序列，与 t 进行比较，找所有子序列的复杂度是 O(2^n)O(2n)，肯定会超时。
因此，我们放弃这种朴素思路。
字符串匹配也不具有二段性质，不可能有 loglog 级别的算法，那么复杂度再往下优化就是 O(n * m)O(n∗m) 的递推 DP 做法了。
动态规划
DP 的状态定义猜测通常是一门经验学科。
但是，对于两个字符串匹配，一个非常通用的状态定义如下：
定义 f[i][j]f[i][j] 为考虑 s 中 [0,i][0,i] 个字符，t 中 [0,j][0,j] 个字符的匹配个数。
那么显然对于某个 f[i][j]f[i][j] 而言，从「最后一步」的匹配进行分析，包含两类决策：
- 不让
s[i]参与匹配，也就是需要让s中 [0,i-1][0,i−1] 个字符去匹配t中的 [0,j][0,j] 字符。此时匹配值为 f[i-1][j]f[i−1][j] - 让
s[i]参与匹配，这时候只需要让s中 [0,i-1][0,i−1] 个字符去匹配t中的 [0,j-1][0,j−1] 字符即可，同时满足s[i]=t[j]。此时匹配值为 f[i-1][j-1]f[i−1][j−1]
最终 f[i][j]f[i][j] 就是两者之和。
代码：
class Solution { public int numDistinct(String s, String t) { // 技巧：往原字符头部插入空格，这样得到 char 数组是从 1 开始 // 同时由于往头部插入相同的（不存在的）字符，不会对结果造成影响，而且可以使得 f[i][0] = 1，可以将 1 这个结果滚动下去 int n = s.length(), m = t.length(); s = " " + s; t = " " + t; char[] cs = s.toCharArray(), ct = t.toCharArray(); // f(i,j) 代表考虑「s 中的下标为 0~i 字符」和「t 中下标为 0~j 字符」是否匹配 int[][] f = new int[n + 1][m + 1]; // 原字符只有小写字符，当往两个字符插入空格之后，f[i][0] = 1 是一个显而易见的初始化条件 for (int i = 0; i <= n; i++) f[i][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { // 包含两种决策： // 不使用 cs[i] 进行匹配，则有 f[i][j] = f[i - 1][j] f[i][j] = f[i - 1][j]; // 使用 cs[i] 进行匹配，则要求 cs[i] == ct[j]，然后有 f[i][j] += f[i - 1][j - 1] if (cs[i] == ct[j]) { f[i][j] += f[i - 1][j - 1]; } } } return f[n][m]; } } 复制代码
- 时间复杂度：O(n * m)O(n∗m)
- 空间复杂度：O(n * m)O(n∗m)
PS. 需要说明的是，由于中间结果会溢出，CPP 中必须使用 long long，而 Java 不用。由于 Java 中 int 的存储机制，只要在运算过程中只要不涉及取 min、取 max 或者其他比较操作的话，中间结果溢出不会影响最终结果。
总结
- 关于字符串匹配，通常有两种（你也可以理解为一种）通用的状态定义：
- f[i][j]f[i][j] 表示「第一个字符
s中 [0,i][0,i] 个字符」与「第二个字符t中 [0,j][0,j] 个字符」的匹配结果 - f[i][j]f[i][j] 表示「第一个字符
s中 [0,i][0,i] 个字符」与「第二个字符t中 [0,j][0,j] 个字符」且 「最后一个字符为t[j]」的匹配结果
- 往两个字符串的头部追加「不存在」的字符，目的是为了能够构造出可以滚动（被累加）下去的初始化值
进阶
事实上，关于字符串匹配问题，还有一道稍稍不同的变形的题目。
也是利用了类似的「通用思路」(状态定义) &「技巧」，然后对匹配过程中的字符进行分情况讨论，学有余力的同学可以看看：
10. 正则表达式匹配 : 如何利用的「等差」性质降低「正则字符串匹配」算法复杂度 ...
最后
这是我们「刷穿 LeetCode」系列文章的第 No.115 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
