[白俊]#2225合分解



質問する


0からNまでの整数にK個を加えてNとする場合は、プログラムを作成して個数を求めます.
加算の順序が変更されると、数が異なる場合(1+2と2+1は異なる場合)になります.1つの数を複数回使用することもできます.

入力


第1行は2つの整数N(1≦N≦200),K(1≦K≦200)を与える.

しゅつりょく


1行目の出力で答えを10000000の残りの部分に分けます.

入力例1

20 2

サンプル出力1

21

に答える


この問題はダイナミックプログラミングで解決できる.
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);
        long[][] dp = new long[N+1][K+1];

        dp[0][0] = 1;

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

        System.out.println(dp[N][K]);
    }
}