115. 不同的子序列
给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。
链接：：https://leetcode.cn/problems/distinct-subsequences/
示例 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
1.状态表示*
dp[i][j] 表⽰：在字符串 s 的 [0, j] 区间内的所有⼦序列中，有多少个 t 字符串 [0,i] 区间内的⼦串.
2.状态转移方程
分析状态转移⽅程的经验就是根据「最后⼀个位置」的状况，分情况讨论。
对于 dp[i][j] ，我们可以根据 s1[i] 与 s2[j] 的字符分情况讨论：
- . 两个字符相同， s1[i] = s2[j] ：那么最⻓公共⼦序列就在 s1 的 [0, i - 1] 以 及 s2 的 [0, j - 1] 区间上找到⼀个最⻓的，然后再加上 s1[i] 即可。因此 dp[i][j] = dp[i - 1][j - 1] + 1 ；
ii. 两个字符不相同， s1[i] != s2[j] ：那么最⻓公共⼦序列⼀定不会同时以 s1[i] 和 s2[j] 结尾。那么我们找最⻓公共⼦序列时，有下⾯三种策略：
去 s1 的 [0, i - 1] 以及 s2 的 [0, j] 区间内找：此时最⼤⻓度为 dp[i - 1][j] ；
去 s1 的 [0, i] 以及 s2 的 [0, j - 1] 区间内找：此时最⼤⻓度为 dp[i ] [j - 1] ；
去s1 的 [0, i - 1] 以及 s2 的 [0, j - 1] 区间内找：此时最⼤⻓度为 dp[i - 1][j - 1]
我们要三者的最⼤值即可。但是我们细细观察会发现，第三种包含在第⼀种和第⼆种情况⾥⾯，但是我们求的是最⼤值，并不影响最终结果。因此只需求前两种情况下的最⼤值即可。
综上，状态转移⽅程为：
if(s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1 ; if(s1[i] != s2[j]) dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
3. 初始化
a. 「空串」是有研究意义的，因此我们将原始 dp 表的规模多加上⼀⾏和⼀列，表⽰空串。
b. 引⼊空串后，⼤⼤的⽅便我们的初始化。
c. 但也要注意「下标的映射关系」，以及⾥⾯的值要「保证后续填表是正确的」。
当 s1 为空时，没有⻓度，同理 s2 也是。因此第⼀⾏和第⼀列⾥⾯的值初始化为 0 即可保证后续填表是正确的.
4. 填表顺序
根据「状态转移⽅程」得：从上往下填写每⼀⾏，每⼀⾏从左往右
5. 返回值
返回 dp[m][n]
代码：
int numDistinct(string s, string t) { int m=t.size(); int n=s.size(); //dp[i][j]表示的是 以0~j范围内的所有s子序列中，有多少0~i的t字串 vector<vector<double>> dp(m+1,vector<double>(n+1)); for(int i=0;i<=n;i++) dp[0][i]=1; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { dp[i][j]+=dp[i][j-1]; if(t[i-1]==s[j-1]) { dp[i][j]+=dp[i-1][j-1]; } } } return dp[m][n]; }
44. 通配符匹配
链接：https://leetcode.cn/problems/wildcard-matching/description/
给你一个输入字符串 (s) 和一个字符模式 § ，请你实现一个支持 ‘?’ 和 ‘’ 匹配规则的通配符匹配：
‘?’ 可以匹配任何单个字符。
'’ 可以匹配任意字符序列（包括空字符序列）。
判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。
示例 1：
输入：s = “aa”, p = “a”
输出：false
解释：“a” 无法匹配 “aa” 整个字符串。
示例 2：
输入：s = “aa”, p = ""
输出：true
解释：'’ 可以匹配任意字符串。
示例 3：
输入：s = “cb”, p = “?a”
输出：false
解释：‘?’ 可以匹配 ‘c’, 但第二个 ‘a’ 无法匹配 ‘b’。
1.状态表示*
dp[i][j] 表⽰： p 字符串 [0, j] 区间内的⼦串能否匹配字符串 s 的 [0, i] 区间内的⼦串
2.状态转移方程
⽼规矩，根据最后⼀个位置的元素，结合题⽬要求，分情况讨论：
- i. 当 s[i] == p[j] 或 p[j] == ‘?’ 的时候，此时两个字符串匹配上了当前的⼀个字符，只能从 dp[i -
1][j - 1] 中看当前字符前⾯的两个⼦串是否匹配。只能继承上个状态中的匹配结果， dp[i][j] = dp[i][j - 1] ；
ii. 当 p[j] == ‘*’ 的时候，此时匹配策略有两种选择：
• ⼀种选择是： * 匹配空字符串，此时相当于它匹配了⼀个寂寞，直接继承状态 dp[i] [j - 1] ，此时 dp[i][j] = dp[i][j -1] ；
• 另⼀种选择是： * 向前匹配 1 ~ n 个字符，直⾄匹配上整个 s1 串。此时相当于从 dp[k][j - 1] (0 <= k <= i) 中所有匹配情况中，选择性继承可以成功的情况。此时 dp[i][j] = dp[k][j - 1] (0 <= k <= i) ；
- iii. 当 p[j] 不是特殊字符，且不与 s[i] 相等时，⽆法匹配。 三种情况加起来，就是所有可能的匹配结果。
综上所述，状态转移⽅程为：
▪ 当 s[i] == p[j] 或 p[j] == ‘?’ 时： dp[i][j] = dp[i][j - 1] ；
▪ 当 p[j] == ‘*’ 时，有多种情况需要讨论： dp[i][j] = dp[k][j - 1] (0 <=k <= i) ；
重难点：
优化：当我们发现，计算⼀个状态的时候，需要⼀个循环才能搞定的时候，我们要想到去优化。优
化的⽅向就是⽤⼀个或者两个状态来表⽰这⼀堆的状态。通常就是把它写下来，然后⽤数学的⽅式
做⼀下等价替换：
当 p[j] == ‘*’ 时，状态转移⽅程为： dp[i][j] = dp[i][j - 1] || dp[i - 1][j - 1] || dp[i - 2][j - 1] …
我们发现 i 是有规律的减⼩的，因此我们去看看 dp[i - 1][j] ：
dp[i - 1][j] = dp[i - 1][j - 1] || dp[i - 2][j - 1] || dp[i - 3][j - 1] …
我们惊奇的发现， dp[i][j] 的状态转移⽅程⾥⾯除了第⼀项以外，其余的都可以⽤ dp[i -
1][j] 替代。因此，我们优化我们的状态转移⽅程为： dp[i][j] = dp[i - 1][j] ||dp[i][j - 1]
3. 初始化
由于 dp 数组的值设置为是否匹配，为了不与答案值混淆，我们需要将整个数组初始化为false 。
由于需要⽤到前⼀⾏和前⼀列的状态，我们初始化第⼀⾏、第⼀列即可。
◦ dp[0][0] 表⽰两个空串能否匹配，答案是显然的，初始化为 true 。
- ◦ 第⼀⾏表⽰ s 是⼀个空串， p 串和空串只有⼀种匹配可能，即 p 串表⽰为 “**" ，此时
也相当于空串匹配上空串。所以，我们可以遍历 p 串，把所有前导为 "” 的 p ⼦串和空串 的 dp 值设为 true 。
- ◦ 第⼀列表⽰ p 是⼀个空串，不可能匹配上 s 串，跟随数组初始化即可。
4. 填表顺序
根据「状态转移⽅程」得：从上往下填写每⼀⾏，每⼀⾏从左往右
5. 返回值
返回 dp[m][n]
代码：
bool isMatch(string s, string p) { int n=s.size(); int m=p.size(); vector<vector<bool>> dp(n+1,vector<bool>(m+1)); //初始化 dp[0][0]=1; for(int i=1;i<=m;i++) { if(p[i-1]=='*') dp[0][i]=1; else break; } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(p[j-1]=='?'||s[i-1]==p[j-1]) { dp[i][j]=dp[i-1][j-1]; } if(p[j-1]=='*') { // for(int z=0;z<=i;z++) // { // if(dp[z][j-1]) // { // dp[i][j]=dp[z][j-1]; // break; // } // } //优化 dp[i][j] = dp[i - 1][j] || dp[i][j - 1]; } } } return dp[n][m]; }
