题解 | #好多牛牛#

题意整理

给定一个字符串S。
求S中有多少子序列等于"niuniu"。

方法一（动态规划）

1.解题思路

假设长度为i-1的字符串s包含N个长度为j的字符串t（"niuniu"）的子序列。如果s的第i个字符不等于t的第j个字符，那么当前状态必定等于前一个状态，即最多只能有N个对应的子序列；如果相等，说明除了这N个子序列，还多出了同时删除s的第i个字符以及t的第j个字符对应状态的子序列。

状态定义： $dp[i][j]$ 表示长度为i的s包含多少个子序列是长度为j的t。
状态初始化：当t为空时，均包含1个对应的子序列。
状态转移：如果相等，说明既可以同时删除s、t的当前字符，又可以只删除s的当前字符,即 $dp[i][j]=dp[i-1][j-1]+dp[i-1][j]$ ；如果不相等，只能删除s的当前字符，即 $dp[i][j]=dp[i-1][j]$ 。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    //取余常数
    int mod=1000000007;

    public int solve (String s) {
        //初始化dp数组，dp[i][j]表示长度为i的s包含多少个子序列是长度为j的t
        int n=s.length();
        String t="niuniu";
        int[][] dp=new int[n+1][7];

        //当t为空时，均包含1个对应的子序列
        for(int i=0;i<=n;i++){
            dp[i][0]=1;
        }

        for(int i=1;i<=n;i++){
            for(int j=1;j<=6;j++){
                /*如果相等，说明既可以同时删除s、t的当前字符，又可以只删除s的当前字符,
                同时删除相当于dp[i-1][j-1]，只删除s的当前字符相当于dp[i-1][j]*/
                if(s.charAt(i-1)==t.charAt(j-1)){
                    dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%mod;
                }
                //如果不相等，只能删除s的当前字符
                else{
                    dp[i][j]=dp[i-1][j];
                }
            }
        }

        return dp[n][6];
    }
}

3.复杂度分析

时间复杂度：循环体最多执行 $6*n$ 次，所以时间复杂度是 $O(n)$ 。
空间复杂度：需要额外大小为 $7*(n+1)$ 的dp数组，所以空间复杂度是 $O(n)$ 。

方法二（空间压缩）

1.解题思路

由于方法一中，字符串S下标每后移一位的状态只与未后移时的状态有关，所以只需要一维的空间存储状态。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    //取余常数
    int mod=1000000007;

    public int solve (String s) {
        //初始化t串
        int n=s.length();
        String t="niuniu";

        //定义dp数组
        int[] dp=new int[7];

        //初始化
        dp[0]=1;

        for(int i=1;i<=n;i++){
            for(int j=1;j<=6;j++){
                //状态转移
                if(s.charAt(i-1)==t.charAt(j-1)){
                    dp[j]=(dp[j]+dp[j-1])%mod;
                }
            }
        }

        return dp[6];
    }
}

3.复杂度分析

时间复杂度：循环体最多执行 $6*n$ 次，所以时间复杂度是 $O(n)$ 。
空间复杂度：需要额外大小为常数级别的dp数组，所以空间复杂度是 $O(1)$ 。