数位dp2

package com.zhang.reflection.面试.算法模版.动态规划;
import java.util.Scanner;
/**
 * 长度不超过nn，且包含子序列“us”的、只由小写字母构成的字符串有多少个？ 答案对10^9+7取模。
 * 所谓子序列，指一个字符串删除部分字符（也可以不删）得到的字符串。
 * 例如，"unoacscc"包含子序列"us"，但"scscucu"则不包含子序列"us"
 */
public class 串 {
    private static final int MOD = 1000000007;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        /**
         * 列举：1.没有u，2.有u 2.1有us 2.2没有us
         * dp[i][0]表示 前i个字符串中没有u的情况
         * dp[i][1]表示 前i个字符串中有u,且不包含us的情况
         * dp[i][2]表示 前i个字符串，包含us子序列的情况
         */
        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个是u
            dp[i][1] = (dp[i-1][1]*25+dp[i-1][0]*1) % MOD;
            // 需要[i-1][2]然后任选一个字符或者[i-1][1]再让i等于s即可
            dp[i][2] = (dp[i-1][2]*26+dp[i-1][1]) % MOD;
            ans = (ans+dp[i][2]) % MOD;
        }
        System.out.println(ans);
    }
}