好多牛牛

给出一个字符串S，牛牛想知道这个字符串有多少个子序列等于"niuniu"
子序列可以通过在原串上删除任意个字符(包括0个字符和全部字符)得到。
为了防止答案过大，答案对1e9+7取模

案例
输入："niuniniu"
返回值：3
说明：
删除第4，5个字符可以得到"niuniu"
删除第5，6个字符可以得到"niuniu"
删除第6，7个字符可以得到"niuniu"

方法一 动态规划

定义一个二维dp数组表示当到达s数组第i位时取到niuniu字符串第j位的所有子序列，然后考虑两种情况

1. s字符串第i位与niuniu第j位相同时，说明当前的结果等于的方案数表示i之前能达到第j位的方案数加上第i位之前能达到第j-1位的方案数(因为第j位是由j-1位加上第j位得来的)，转移式为
2. s字符串第j位与niuniu第j位不同时，直接取前面能达到第j位的方案数也就是
   

class Solution {
public:
    long long dp[100010][10], mod = 1e9 + 7;
    string ss = " niuniu";
    int solve(string s) {
        // write code here
        int n = s.length();
        for(int i = 0; i <= n; i ++) dp[i][0] = 1;
        for(int i = 0; i < n; i ++){ //遍历s字符串
            for(int j = 1; j <= 6; j ++){ //遍历niuniu字符串
                if(ss[j] == s[i]) dp[i + 1][j] = dp[i][j] + dp[i][j - 1]; //如果当前s的字符与niuniu匹配
                else dp[i + 1][j] = dp[i][j]; // 如果不匹配
                dp[i + 1][j] %= mod;
            }
        }
        return dp[n][6];
    }
};

时间复杂度： 总复杂度为niuniu的长度乘s字符长度
空间复杂度: 最多会使用s字符串长度*niuniu字符串长度的空间

方法二 动态规划-空间压缩

该方法是方法一的优化,通过方法一的图片能发现每次只需要维护niuniu字符串长度的数组即可，对于每个s字符串i字符如果与niuniu第j位相同则将第j - 1位的方案数加上第j位的方案数即可转移式为：

class Solution {
public:
    long long dp[110000];
    long long mod = 1e9 + 7;
    string ss = "niuniu";
    int solve(string s) {
        // write code here
        dp[0] = 1;
        for(int i = 1; i <= s.length(); i ++){
            for(int j = 1; j <= 6; j ++){
                if(ss[j - 1] == s[i - 1]) { //如果相同则更新dp数组
                    dp[j] = (dp[j - 1] + dp[j]) % mod;
                }
            }
        }
        return dp[6];
    }
};

时间复杂度: 总复杂度为niuniu的长度乘s字符长度
空间复杂度: dp数组最多会用到niuniu字符串的长度