【错题集-编程题】mari和shiny（动态规划-多源状态线性 dp）

题目对应链接：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] 可以有两部分组成：

1. 一部分是用 str[i - 1] 来匹配，那么个数为 dp[i - 1][j - 1]。即不需要考虑当前 str 子串和 t 子串的最后一位字母，所以只需要 dp[i-1][j-1]。
2. 一部分是不用 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）