统计某一子序列的出现次数 好多牛牛

参考 这篇csdn博客

dp数组

int[][] dp = new int[s.length][pattern.length]

含义

dp[i][j] 表示从 目标s[0:i +1] 中 序列pattern[0:j +1] 的 出现次数

递推公式

dp[i][j] = dp[i-1][j] + dp[i-1][j-1], 当s[i]==s[j]时
              或 dp[i-1][j], 当s[i]!=s[j]时

import java.util.*;

public class Solution {
    public int solve (String s) {
        String pattern = "niuniu";

        int idx = 0;
        int[][] dp = new int[2][pattern.length()+1];

        dp[0][0] = 1;
        dp[1][0] = 1;

        for(int i = 0; i < s.length(); ++i){
            for(int j=1;j<=pattern.length();++j){
                dp[idx][j] = (dp[1-idx][j] + (s.charAt(i) == pattern.charAt(j-1) ? dp[1-idx][j-1] : 0)) % (int)(1e9+7);
            }
            idx = 1 - idx;
        }

        return dp[idx][pattern.length()];
    }
}