java 牛客网之[动态规划 中等]NC20 串

java 牛客网之[动态规划 中等]NC20 串

题目的链接在这里：https://www.nowcoder.com/practice/01c35f01fb7343fe9fc16139562f78ed

目录

• 题目大意
• 一、示意图
• 二、解题思路
• • 数位dp

---

题目大意 长度不超过nn，且包含子序列“us”的、只由小写字母构成的字符串有多少个？ 答案对10^9+710 9 +7取模。 所谓子序列，指一个字符串删除部分字符（也可以不删）得到的字符串。 例如，"unoacscc"包含子序列"us"，但"scscucu"则不包含子序列"us"

---

一、示意图

二、解题思路

数位dp

数位dp

代码如下：

import java.util.*;

public class  Main{
    final static long MOD=1000000007;
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        
        long[][] dp=new long[n+1][3];
        //然后开始初始化 26个字母中排除 u
        dp[1][0]=25;
        dp[1][1]=1;
        dp[1][2]=0;
        long ans=0;
        for(int i=2;i<=n;i++){
            //dp[i][0] 就是前i个没有u的情况 肯定是需要i-1个字符没有u然后第i个字符也不是u的情况
            dp[i][0]=25*dp[i-1][0]%MOD;
            //dp[i][1] 就是前i-1个有u没有s 并且第i个只要不是s就行 他还可以是 前i-1个
            dp[i][1]=(dp[i-1][1]*25+dp[i-1][0])%MOD;
            //需要[i-1][2]然后任选一个字符 或者 [i-1][1]再让i等于u即可
            dp[i][2]=(dp[i-1][2]*26+dp[i-1][1])%MOD;
            ans=(ans+dp[i][2])%MOD;
        }
        System.out.println(ans);
    }
}