[白準/DP]11057号上り坂数(JAVA)

質問する

に答える

dp[i][j]:i桁の最後の数字がjの場合の上り坂の数i-1の長さの上り坂数の最後にjの数字を加えてdp[i][j]の配列を満たす.このとき、countAddable()は、upperBound以下の数字を最後の数字とするi-1の長さの上り坂数を求める.
最終結果はdp[n][0]からdp[n][9]の合計が正解です.

コード#コード#

import java.io.*;

public class Main {

    private static final int MAXIMUM = 1000;
    private static final int MOD = 10007;
    private static final int NUMBERS = 10;

    private static int n;
    private static int[][] dp = new int[MAXIMUM + 1][NUMBERS];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        dp();
        bw.append(String.valueOf(sum(dp[n])));

        br.close();
        bw.close();
    }

    private static void dp() {
        for (int i = 0; i < NUMBERS; i++) dp[1][i] = 1;
        for (int i = 2; i <= n; i++)
            for (int j = 0; j < NUMBERS; j++)
                dp[i][j] = countAddable(dp[i - 1], j) % MOD;
    }

    private static int countAddable(int[] arr, int upperBound) {
        int count = 0;
        for (int i = 0; i <= upperBound; i++) count = (count + arr[i]) % MOD;
        return count;
    }

    private static int sum(int[] arr) {
        int sum = 0;
        for (int val : arr) sum = (sum + val) % MOD;
        return sum;
    }
}