子序列问题具有子问题性质，要注意字符顺序

思路

看例子我以为这是一个乘法组合问题，于是统计三个字符的次数，返回其乘积，通过了40%。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 300010;
char s[N];

signed main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> s[i];
    int a = 0, b = 0, c = 0;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == 's') a++;
        else if (s[i] == 'h') b++;
        else if (s[i] == 'y') c++;
    }
    cout << a * b * c << endl;
    return 0;
}

但这种做法忽略了字符的顺序要求（即 's' 在 'h' 之前，'h' 在 'y' 之前）。在一个字符串中，"shy" 是一个子序列，需要满足顺序条件。

正确的做法是逐步统计每个字符 's'、'h' 和 'y' 的出现，并根据子序列的定义累积可能的子序列数量。需要从左到右遍历字符串，并在遇到 'y' 时，统计当前之前所有可能的 'shy' 子序列。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 300010;
char s[N];

signed main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> s[i];
    int count_s = 0, count_sh = 0, count_shy = 0;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == 's') count_s++;
        else if (s[i] == 'h') count_sh += count_s;
        else if (s[i] == 'y') count_shy += count_sh;
    }
    cout << count_shy << endl;
    return 0;
}

时间复杂度： $O(n)$ 。
空间复杂度： $O(1)$ 。

DFS

子序列是一个典型的具有子问题的模型，考虑用DFS把大问题化为小问题。通过递归枚举字符串的每一个字符，并检查是否能形成子序列 "shy"。

dfs(idx, stage, n) 表示从字符串的第 idx 个字符开始，寻找第 stage 个字符（0 对应 's'，1 对应 'h'，2 对应 'y'）的子序列的数量。

如果 stage 达到 3，表示找到了一个完整的 "shy" 子序列，返回 1。
如果 idx 达到字符串长度 n，表示已经遍历完所有字符，返回 0。
每次递归调用 dfs(idx + 1, stage, n) 表示不选择当前字符。
如果当前字符符合要求（stage 对应的字符是 s[idx]），则递归调用 dfs(idx + 1, stage + 1, n) 表示选择当前字符。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 300010;
char s[N];
int memo[N][3];
int dfs(int idx, int stage, int n)
{
    // 找到了一个完整的 "shy" 子序列
    if (stage == 3) return 1;
    // 遍历完所有字符后未能找到完整的 "shy" 子序列
    if (idx == n) return 0;
    if (memo[idx][stage] != -1) return memo[idx][stage];
    int res = dfs(idx + 1, stage, n); // 不选当前字符
    if ((stage == 0 && s[idx] == 's') ||
        (stage == 1 && s[idx] == 'h') ||
        (stage == 2 && s[idx] == 'y'))
    {
        res += dfs(idx + 1, stage + 1, n); // 选当前字符
    }
    return memo[idx][stage] = res;
}

signed main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> s[i];
    memset(memo, -1, sizeof(memo));
    cout << dfs(0, 0, n) << endl;
    return 0;
}

时间复杂度： $O(n)$ 。
空间复杂度： $O(n)$ 。

考试时一开始看到子序列就想用DFS求总路径条数，但是不知道怎么构造参数列表，问题的关键在于捕捉子序列中字符的先后次序这一要素，就能往子问题递归了。

动态规划

将记忆化搜索翻译成递推。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 300010;
char s[N];
int dp[N][4];

signed main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> s[i];
    dp[0][0] = 1;
    for (int i = 0; i < n; i++)
    {
        for (int stage = 0; stage < 4; stage++)
        {
            // 当前 dp[i][stage] 的值直接转移到 dp[i+1][stage]
            dp[i + 1][stage] += dp[i][stage];
            // 选当前字符的情况
            if (stage < 3)
            {
                if ((stage == 0 && s[i] == 's') ||
                    (stage == 1 && s[i] == 'h') ||
                    (stage == 2 && s[i] == 'y'))
                {
                    dp[i + 1][stage + 1] += dp[i][stage];
                }
            }
        }
    }
    cout << dp[n][3] << endl;
    return 0;
}