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

简介: 【错题集-编程题】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)


相关文章
|
8月前
|
存储 人工智能 算法
【算法分析与设计】动态规划(下)(一)
【算法分析与设计】动态规划(下)
|
1月前
【编程题-错题集】分割等和子集(动态规划 - 01背包)
【编程题-错题集】分割等和子集(动态规划 - 01背包)
|
15天前
|
存储 索引
每日刷题——相遇、宝石(模拟+数学)、相助(模拟+数组)、相依(dp的优化)
每日刷题——相遇、宝石(模拟+数学)、相助(模拟+数组)、相依(dp的优化)
14 1
|
1月前
|
算法 测试技术 C++
【动态规划 状态机dp 性能优化】3098. 求出所有子序列的能量和
【动态规划 状态机dp 性能优化】3098. 求出所有子序列的能量和
【动态规划 状态机dp 性能优化】3098. 求出所有子序列的能量和
|
1月前
【错题集-编程题】不相邻取数(动态规划 - 线性 dp)
【错题集-编程题】不相邻取数(动态规划 - 线性 dp)
|
1月前
|
存储
【错题集-编程题】合唱团(动态规划 - 线性 dp)
【错题集-编程题】合唱团(动态规划 - 线性 dp)
|
1月前
【错题集-编程题】删除相邻数字的最大分数(动态规划 - 线性 dp)
【错题集-编程题】删除相邻数字的最大分数(动态规划 - 线性 dp)
|
1月前
【编程题-错题集】连续子数组最大和(动态规划 - 线性 dp)
【编程题-错题集】连续子数组最大和(动态规划 - 线性 dp)
|
8月前
|
存储 算法
【算法分析与设计】动态规划(下)(三)
【算法分析与设计】动态规划(下)
|
8月前
|
消息中间件 人工智能 算法
【算法分析与设计】动态规划(下)(二)
【算法分析与设计】动态规划(下)