位数问题动态规划（java）

解题思路: 代码使用了动态规划来计算N位数中包含偶数个数字3的数的个数，并将结果对12345取余
注意事项:

参考代码:

import java.util.Scanner;

public class 位数问题 {
    private static final int MOD = 12345;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 你可以将这里的N替换成你需要的位数
        long[][] dp = new long[N + 1][2];

        // 初始化
        dp[1][0] = 8; // 除了3以外的数字个数,首位不可以为0
        dp[1][1] = 1; // 只有数字3

        // 动态规划填表
        for (int i = 2; i <= N; i++) {
            dp[i][0] = (dp[i - 1][0] * 9 + dp[i - 1][1]) % MOD;
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][1] * 9) % MOD;
            //dp[i][0] 表示i位数中包含偶数个3的数的个数。
            //dp[i][1] 表示i位数中包含奇数个3的数的个数。
        }

        // 输出结果，N位数中包含偶数个3的数的个数对12345取余的值
        System.out.println(dp[N][0]);
    }
}