NC557 题解 | #好多牛牛#

题意分析

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

思路分析

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

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

  • 我们先定义状态方程dp[i][j],表示前i个字符中以"niuniu"这个字符的第j个字符结尾的子序列的个数。然后就可以进行一个正常的转移了,转移方程如下
dp[i][j]={dp[i1][j]+dp[i][j]s[i]==c[j]dp[i1][j]s[i]!=c[j]dp[i][j]=\left\{ \begin{matrix} dp[i-1][j]+dp[i][j] && s[i]==c[j] \\ dp[i-1][j] && s[i]!=c[j] \end{matrix} \right.
  • 我们可以发现每个状态只和前面那个状态有关,所以我们可以利用滚动数组进行优化,将状态分为奇状态和偶状态。然后进行相关转移。

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

alt

  • 代码如下
    • 需要循环字符串的长度次,然后每次需要和题目给的"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;
    }
};