题解 | #好多牛牛#

关键:f[i][j]这个数组表示改造字符串前i个字符使其与niuniu这个字符串前j个相同的个数。则最终的结果就是f[n][6],即s前n个字符共可以改造几次得到niuniu这个字符串。

初始化

  for(int i=0;i<=n;i++)
    {
            f[i][0]=1;
    }

该初始化表示将字符串前i个变为空字符的方法有几种。显然只有一种方案即全部清空。

状态转移方程:

当s[i]==s1[j]时，说明这个是s[i]字符可以出现在s1字符串中。这个字符有两种选择要么让它加入构成niuniu，要么删除它。所以f[i][j]=f[i-1][j]+f[i-1][j-1],其中f[i-1][j]表示用前i-1个字符构成niuniu前j个字符串的所有方案的个数，即不要第i个字符。而f[i-1][j-1]表示前i-1个字符构成niuniu的前j-1个字符串的所有方案的个数，这是说明留下了s[i]。

当s[i]!=s1[j]，则s[i]只能被舍弃，即f[i][j]=f[i-1][j]。

const int N=10010;
int f[N][10];
long long mod=1e9+7;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    int solve(string s) {
        int n=s.size();
        string s1=" niuniu";
        cout<<s1[4]<<endl;
        //f[i][j]表示从字符串s的0到i与s1的0到j匹配的字符串的个数
        for(int i=0;i<=n;i++)
        {
            f[i][0]=1;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=6;j++)
            {
                if(s[i-1]==s1[j])//当第i个字符与niuniu的第j+1个匹配的时候有两种选择
                {
                    f[i][j]=f[i-1][j]+f[i-1][j-1];//使用s[i]匹配为f[i][j]，不使用为f[i][j-1]
                }
                else
                {
                    f[i][j]=f[i-1][j];
                }
                f[i][j] %= mod;
            }
        }
        return f[n][6];
        // write code here
    
    }
};