• 考虑通用的问题，给定一个字符串S和模式串T，求S中有多少个子序列=T。

• 设dp[i+1][j+1]表示串S[0,i]中有多少个子序列=T[0,j]。那么状态转移方程为：
• 若S[i] != T[j]，那么dp[i+1][j+1] = dp[i][j+1] ，表示S[0,i-1]中T[0,j]出现的次数。
• 若S[i] == T[j]，那么dp[i+1][j+1] = dp[i][j+1] + dp[i][j]，除了包含S[0,i-1]中T[0,j]出现的次数，由于S[i]==T[j]，那么若S[0,i-1]==T[0,j-1]，那么会有新的T[0,j]匹配，次数即dp[i][j]。
• 注意到上述转移方程中，第一维中，dp[i+1]只和dp[i]有关，因此我们可以去掉第一维。那么状态转移方程变为：
• 若S[i] != T[j]，那么dp[j+1] = dp[j+1]
  
• 若S[i] == T[j]，那么dp[j+1] = dp[j+1] + dp[j]
  
• 需要注意的是，这时候在枚举j时，需要逆序枚举，因为二维转移方程中，j+1依赖上一维的j和j+1，改为1维后，若正序更新j，那么若更新完dp[1]，然后更新dp[2]，若dp[2] = dp[2] + dp[1]，这里需要的dp[1]是上一轮的dp[1]，而正序更新会导致dp[1]已经更新过，那么显然是错误的。而逆序更新就没问题。
• 下面是一维数组的版本。

• const int mod = 1e9+7;
  const string pat = "niuniu";
  
  class Solution {
  public:
      /**
       * 好多牛牛
       * @param s string字符串
       * @return int整型
       */
      int solve(string& s) {
          // write code here
          int pLen = pat.size();
          vector<int> dp(pLen+1);
          dp[0] = 1;
          for(const auto& c:s){
              for(int j=pLen-1;j>=0;j--){
                  if(c==pat[j]){
                      dp[j+1] = (dp[j+1] + dp[j])%mod;
                  }
              }
          }
          return dp[pLen];
      }
  };
  

  
  

• 当然，由于pat=“niuniu”比较短，我们也可以直接暴力写动态规划

  const int mod = 1e9+7;
  
  class Solution {
  public:
      /**
       * 好多牛牛
       * @param s string字符串
       * @return int整型
       */
      int solve(string& s) {
          // write code here
          int sLen = s.size();
          vector<int> dp(5);
          for(int i=0;i<sLen;i++){
              switch(s[i]){
                  case 'n': dp[0] = (dp[0]+1)%mod; dp[3] = (dp[3]+dp[2])%mod;break;
                  case 'i': dp[1] = (dp[0]+dp[1])%mod; dp[4] = (dp[3]+dp[4])%mod;break;
                  case 'u': dp[2] = (dp[1]+dp[2])%mod; dp[5] = (dp[4]+dp[5])%mod;break;
                  default: break;
              }
          }
          return dp[5];
      }
  };

  
  

class Solution {
public:
    /**
     * 好多牛牛
     * @param s string字符串 
     * @return int整型
     */
    int solve(string s) {
        string t = "niuniu";
        int M = 1e9+7, n=s.length(), m=t.length();
        long dp[n];
        memset(dp, 0, sizeof(dp));
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(s[i]==t[j]){
                    dp[j] += (j==0 ? 1 : dp[j-1]);
                    dp[j] %= M;
                }
        return dp[m-1];
    }
};

class Solution {
public:
    int solve(string s) 
    {
        int count[6] = { 0,0,0,0,0,0 };  //分别记录已遍历序列中"n","ni","niu","niun","niuni","niuniu"的个数
        for (int i = 0; i < s.size(); ++i)
        {
            switch (s[i])
            {
            case 'n':++count[0]; count[3] += count[2];
                count[0] %= 1000000007;
                count[3] %= 1000000007;
                break;             //当前字符是'n'时,"n"与"niun"数量改变
            case 'i':count[1] += count[0]; count[4] += count[3]; 
                count[1] %= 1000000007;
                count[4] %= 1000000007;
                break;             //当前字符是'i'时,"ni"与"niuni"数量改变
            case 'u':count[2] += count[1]; count[5] += count[4]; 
                count[2] %= 1000000007;
                count[5] %= 1000000007;
                break;             //当前字符是'u'时,"niu"与"niuniu"数量改变
            } 
        }
        return count[5];
    }
};

memset(f, 0, sizeof(f));
f[0] = 1;
string a = "*niuniu";
for(int i = 1; i <= s.size(); i++){
    for(int j = 1; j <= 6; j++){
        if(s[i-1] == a[j]){
            f[j] += f[j-1];
            f[j] %= MOD;
        }
    }
}
return f[6];

1 1 1 1 1 1 1 1 1 1 *
1 1 1 2 2 3 3 3 0 0 n
0 1 1 1 3 3 6 6 0 0 i 
0 0 1 1 1 1 1 7 0 0 u
0 0 0 1 1 2 2 2 0 0 n
0 0 0 0 1 1 3 3 0 0 i
0 0 0 0 0 0 0 3 0 0 u
n i u n i n i u

匹配的子串数目（动态规划）

• 令dp数组为主串s的长度为i的前缀s[0, i]中和模式串pat("niuniu")任意长度前缀匹配的数目

• 那么状态转移方程即为

  • dp[j] += dp[j - 1] if s[i] == pat[j]

  • 其中当j = 0时，dp[0] += 1, 不妨在dp[0]的前面插入一个1， 以使代码更加整洁

    int solve(string s) {
        // write code here
        int n = s.size();
        if(n < 6) return 0;
        string pat = "niuniu";
        size_t plen = pat.size();
    
        vector<int> dp(plen + 1, 0);
        dp[0] = 1;
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < plen; ++j)
            {
                if(s[i] == pat[j])
                dp[j + 1] += dp[j];
                dp[j + 1] %= 1000000007;
            }
        }
    
        return dp[plen];
    }

import java.util.*;


public class Solution {
    /**
     * 好多牛牛
     * @param s string字符串
     * @return int整型
     */
    public int solve (String s) {
        String niu = "niuniu";
        int n = s.length();
        int m = niu.length();
        int mo = 1000000007;
        int[] dp = new int[m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(s.charAt(i) == niu.charAt(j)){
                    dp[j] += (j==0 ? 1 : dp[j-1]);
                    dp[j] %= mo;
                }
            }
        }

        return dp[m-1];
    }
}

public class Solution {
    /**
     * 好多牛牛
     * @param s string字符串 
     * @return int整型
     */
    public int solve (String s) {
        // write code here
        int M = 1000000007;
        String t = "niuniu";
        int m = s.length();
        int n = t.length();
        int[][] dp = new int[n+1][m+1];
        for(int j = 0; j <= m;j++){
            dp[0][j] = 1;
        }
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=m;j++){
                if(s.charAt(j-1) == t.charAt(i-1)){
                    dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
                    dp[i][j] %= M;
                }else{
                    dp[i][j] = dp[i][j-1] % M;
                }
            }
        }
        return dp[n][m]%M;
    }
}