题解 | #好多牛牛#

思路：

题目的主要信息：

从字符串s的子序列中找到等于"niuniu"的子序列数
子序列即原串的删去任意个字符（包括0和全部）
字符串s长度默认不小于10，结果需取模1e9+7

方法一：动态规划
具体做法：
我们用 $dp[i][j]$ 表示以i-1为结尾的s子序列中出现以j-1为结尾的字符串t的个数，对于某一个字符，我们比较，如果其相等，我们选择匹配或者不匹配（不匹配就是删去这个，另外匹配的意思），二者相加即可；如果不相等，那只能选不匹配，于是转移方程就是这两个:

字符相等： $dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1]$

字符不相等： $dp[i][j] = dp[i][j - 1]$

class Solution {
public:
  int solve(string s) {
      int mod = 1e9 + 7;
      int n = s.length();
      vector<vector<int> > dp(7, vector<int>(n + 1, 0));//以i-1为结尾的字符串s子序列中出现以j-1为结尾的字符串t的个数为dp[i][j]
      for(int i = 0; i <= n; i++)
          dp[0][i] = 1;
      string t = "niuniu";
      for(int i = 1; i <= 6; i++){
          for(int j = 1; j <= n; j++){
              if(t[i - 1] == s[j - 1]) //比较是否相等
                  dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1]; //匹配或者不匹配
              else{
                  dp[i][j] = dp[i][j - 1]; //不匹配
              }
          }
      }
      return dp[6][n];
  }
};

复杂度分析：

时间复杂度： $O(6*n)=O(n)$ ，相当于一次遍历
空间复杂度： $O(n)$ ，7个一维数组

方法二：动态规划空间改进
具体做法：
方法一我们可以看到，我们只用到了 $i$ 和 $i-1$ ，于是我们可以考虑将6次的循环放入内部，每次都计算该为下以某个字符结尾的子序列数量，一直累加到字符串s的结尾。如图所示，图中前半部分是遍历所有字符，后半部分只显示相同的字符：
图片说明

class Solution {
public:
    int solve(string s) {
        int mod = 1e9 + 7;
        int n = s.length();
        vector<int> dp(6, 0); //dp[j]表示截至到访问的字符串i字符，字符串(0,j)出现在子序列的次数
        string t = "niuniu";
        for(int i = 0; i < n; i++){
            for(int j = 0; j < 6; j++){
                if(s[i] == t[j]){  //相等
                    if(j == 0){
                        dp[j]++;
                        dp[j] %= mod;
                    }else{
                        dp[j] += dp[j - 1]; 
                        dp[j] %= mod;
                    }
                }
            }
        }
        return dp[5];
    }
};

复杂度分析：

时间复杂度： $O(6*n)=O(n)$ ，相当于一次遍历
空间复杂度： $O(1)$ ，常数个变量，无额外空间