白駿2225号(Java)

DP
Javaで白俊2225号を解読しました.
あなたのDPへ
質問リンクを添付します.
https://www.acmicpc.net/problem/2225

点火式を探す
最も多く出現する形なので、複数の数字の和を2つの和に変換する原理を利用して点火式を探そうとしたが、結局見つからなかった.
人の解答を見るたびに「あ…」しかしいずれにしても、解決できなかったのは解決できなかった......ううう0~N個からK個を用いた点火式を作成するため、Nを発表した.int[][] dp = new int[K+1][N+1]はdp[k][n]の数字であり、kを生成できる数を示す.
2つの数だけでnが製造できると考えられる場合、以下の点火式を導出することができる.n dp[k][n] = dp[k-1][n] + dp[k][n-1]個の数でk-1を作り、nを加えればいいです.0個の数でkを作り、n-1を加えればいいです.
コードは以下の通りです.

import java.io.*;
import java.util.StringTokenizer;

public class boj2225 {
    static int N,K;
    static int[][] dp;

    static Integer solution(){
        dp = new int[K+1][N+1];
        for(int i=1; i<=K; i++)
            dp[i][1] = i;

        for(int i=1; i<=N; i++)
            dp[1][i] = 1;

        for(int i=2; i<=K; i++){
            for(int j=2; j<=N; j++){
                dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % 1000000000;
            }
        }
        return dp[K][N];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(bfr.readLine());
        N = Integer.parseInt(stk.nextToken());
        K = Integer.parseInt(stk.nextToken());
        System.out.println(solution());
    }
}

DPをちゃんと解きたい
先生.