[算法题]mari和shiny

题目链接: mari和shiny

动态规划求解, 单纯定义一个状态表示不够, 需要定义三个状态表示, 分别为:

• s[i]: 表示区间 [0, i] 中最多有多少个 's'. 其状态转移方程可分为两种情况: 1) 当遍历到的字符是 's' 时为 s[i] = s[i - 1] + 1, 否则为 s[i] = s[i - 1].
• h[i]: 表示区间 [0, i] 中最多有多少个 "sh". 其状态转移方程可分为两种情况: 1)当遍历到的字符是 'h' 时为 h[i] = s[i - 1] + h[i - 1], 否则为 h[i] = h[i - 1].
• y[i]: 表示区间 [0, i] 中最多有多少个 "shy". 其状态转移方程可分为两种情况: 1)当遍历到的字符是 'y' 时为 y[i] = h[i - 1] + y[i - 1], 否则为 y[i] = y[i - 1].

正常来写要开三个数组存放每次的结果, 但是可以使用三个变量来分别记录结果, 达到空间优化的目的, 题解代码如下:

#include <iostream>
using namespace std;

int main()
{
    int n = 0;
    cin >> n;
    string str;
    cin >> str;
    
    long s = 0; 
    long h = 0; 
    long y = 0; 
    
    for(int i = 0; i < n; ++i)
    {
        if(str[i] == 's')
        {
            s++;
        }
        else if(str[i] == 'h')
        {
            h += s;
        }
        else if(str[i] == 'y')
        {
            y += h;
        }
    }
    
    cout << y << endl;
    return 0;
}