NC557 题解 | #好多牛牛#

题意分析

• 给出一个字符串，需要找出里面$\mathrm{"}niuniu\mathrm{"}"niuniu"$这个字序列的数量。子序列可以通过在原串上删除任意个字符(包括0个字符和全部字符)得到

思路分析

• 这里，我介绍两种空间优化的方法

解法一 动态规划 + 滚动数组

• 我们先定义状态方程dp[i][j]，表示前i个字符中以"niuniu"这个字符的第j个字符结尾的子序列的个数。然后就可以进行一个正常的转移了，转移方程如下

• 我们可以发现每个状态只和前面那个状态有关，所以我们可以利用滚动数组进行优化，将状态分为奇状态和偶状态。然后进行相关转移。

• 滚动数组原理大致如下，就是当前的状态由上一个状态转移过来，而不和其他状态有关联

• 代码如下
  • 需要循环字符串的长度次，然后每次需要和题目给的"niuniu"的每个字符进行比较，时间复杂度为$O(6n)O(6n)$,可以看作是$O(n)O(n)$
  • 利用滚动数组进行了优化，空间复杂度为$O(12)O(12)$,可以看作是$O(1)O(1)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    typedef long long ll;
    ll dp[2][10];
    const int mod=1e9+7;
    string c=" niuniu";
    int solve(string s) {
        // write code here
        memset(dp,0,sizeof(dp));
        int n=s.size();
        // 初始化条件
        dp[0][0]=1;
        for(int i=0;i<n;i++){
            // 当前这一维的变量都清零，防止之前计算的结果干扰
            for(int j=1;j<=6;j++){
                dp[(i+1)&1][j]=0;
            }
            dp[(i+1)&1][0]=1;
            for(int j=1;j<=6;j++){
                // 如果相等，那么就上一维转移过来+这一维的
                if(s[i]==c[j]){
                    dp[(i+1)&1][j]=dp[i&1][j]+dp[i&1][j-1];
                }else{
                    // 如果不相等，那么直接上一维转移过来
                    dp[(i+1)&1][j]=dp[i&1][j];
                }
            }
        }
        return (dp[n&1][6]%mod+mod)%mod;
    }
};

解法二 动态规划 + 空间优化

• 由第一种解法可以知道，其实我们都没有必要定义二维的状态转移方程，我们可以将第二维用判断进行替代，也就是直接定义num[i]表示以"niuniu"中第i个字符结尾的子序列的个数，然后我们进行判断，如果当前的字符为n,那么可以是“niuniu”中第一个字符，也可以是第三个字符，字符i和字符u同理。进行对应的转移即可。

• 代码如下

  • 需要循环字符串的长度次，时间复杂度为$O(n)O(n)$
  • 对空间进行了优化，只需要大小为6的数组空间，空间复杂度为$O(6)O(6)$,可以看作是$O(1)O(1)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    typedef long long ll;
    ll sum[10];
    const int mod=1e9+7;
    int solve(string s) {
        // write code here
        memset(sum,0,sizeof(sum));
        int n=s.size();
        
        for(auto x:s){
        	// 可能是第一个字符或者第三个字符
            if(x=='n'){
                sum[4]+=sum[3];
                sum[1]++;
            }
            // 可能是第二个字符或者第四个字符
            if(x=='i'){
                sum[5]+=sum[4];
                sum[2]+=sum[1];
            }
            // 可能是第三个字符或者第六个字符
            if(x=='u'){
                sum[6]+=sum[5];
                sum[3]+=sum[2];
            }
        }
        return (sum[6]%mod+mod)%mod;
    }
};