题目对应链接：mari和shiny (nowcoder.com)
一、分析题目
1、线性 dp
在维护 i 位置之前，⼀共有多少个 "s" "sh" ，然后更新 "shy" 的个数。
（1）状态表示
- s[i]：字符串 str 中 [0, i] 区间内有多少个 "s"。
- h[i]：字符串 str 中 [0, i] 区间内有多少个 "sh"。
- y[i]：字符串 str 中 [0, i] 区间内有多少个 "shy。
（2）状态转移方程
（3）返回值
y[n - 1]（字符串 str 中 [0, n-1] 区间内有多少个 "shy"）
2、二维 dp
这道题目如果不是子序列，而是要求连续序列的，那就可以考虑用 KMP。
（1）dp[i][j] 含义
- string t="shy"
dp[i][j]：以 i-1 为结尾的 str 子序列中出现以 j-1 为结尾的 t 的个数为 dp[i][j]。
（2）递推关系
- str[i - 1] 与 t[j - 1]相等
- str[i - 1] 与 t[j - 1] 不相等
当 str[i - 1] 与 t[j - 1]相等时，dp[i][j] 可以有两部分组成：
- 一部分是用 str[i - 1] 来匹配，那么个数为 dp[i - 1][j - 1]。即不需要考虑当前 str 子串和 t 子串的最后一位字母，所以只需要 dp[i-1][j-1]。
- 一部分是不用 str[i - 1] 来匹配，个数为 dp[i - 1][j]。
为什么还要考虑不用 str[i - 1] 来匹配，都相同了指定要匹配？
例如： str：shyy 和 t：shy ，str[3] 和 t[2] 是相同的，但是字符串 str 也可以不用 str[3] 来匹配，即用 str[0]str[1]str[2] 组成的 "shy"。当然也可以用 str[3] 来匹配，即：str[0]str[1]str[3] 组成的 "shy"。
所以，当 str[i - 1] 与 t[j - 1] 相等时，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
当 str[i - 1] 与 t[j - 1] 不相等时，dp[i][j] 只有一部分组成，不用 str[i - 1] 来匹配（就是模拟在 str 中删除这个元素），即：dp[i - 1][j]，所以递推公式为：dp[i][j] = dp[i - 1][j];
为什么只考虑 “不用 str[i - 1] 来匹配” 这种情况， 不考虑 “不用 t[j - 1] 来匹配” 的情况呢？
这里要明确，我们求的是 str 中有多少个 t，而不是求 t 中有多少个 str，所以只考虑 str 中删除元素的情况，即不用 str[i - 1] 来匹配 的情况。
（3）初始化
- dp[i][0] 表示：以 i-1 为结尾的 str 可以随便删除元素，出现空字符串的个数。所以，dp[i][0] 一定都是 1，因为也就是把以 i-1 为结尾的 str，删除所有元素，出现空字符串的个数就是 1。
- dp[0][j] 表示：空字符串 str 可以随便删除元素，出现以 j-1 为结尾的字符串 t 的个数。所以，dp[0][j] 一定都是 0，因为 str 如论如何也变成不了 t。
- dp[0][0] 表示：空字符串 str 可以删除 0 个元素，变成空字符串 t。所以，dp[0][0] = 1。
（4）遍历顺序
从上到下，从左到右。
二、代码
1、写法一（多源状态线性 dp - 空间优化）
#include <iostream> #include <string> using namespace std; int n; string str; int main() { cin >> n >> str; long long s = 0, h = 0, y = 0; for(int i = 0; i < n; i++) { char ch = str[i]; if(ch == 's') s++; else if(ch == 'h') h += s; else if(ch == 'y') y += h; } cout << y << endl; return 0; }
2、写法二
#include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; string str; cin >> str; string t="shy"; int m=t.size(); vector<vector<long long>> dp(n+1, vector<long long>(m+1)); for(int i=0; i<=n; i++) dp[i][0]=1; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { if(str[i-1]==t[j-1]) dp[i][j]=dp[i-1][j-1]+dp[i-1][j]; else dp[i][j]=dp[i-1][j]; } } cout << dp[n][m] << endl; return 0; }
三、反思与改进
看完题解之后感觉这道题目之前做过，但估计那时候没完全理解。虽然动态规划的代码很精简，但其实里面每一个变量的含义及其递推都不简单，深入分析之后才能明白其中每一个变量的的含义。这道题目我是用 dfs 做的，刚拿到这道题时，想到了之前做过的组合总和，但后面发现这样做数据量太大，只过了 40% 的样例，很明显超出了题目所给的数据范围。后面做题要尝试多用不同的角度去思考问题，多尝试，自然就有经验了。这道题目之前也做过类似的，不过其中状态的递推关系不太好理解，可以反复多做几次：115. 不同的子序列 - 力扣（LeetCode）
