P1192 台阶问题

题目描述

有N 级台阶，你一开始在底部，每次可以向上迈

1∼K 级台阶，问到达第

N 级台阶有多少种不同方式。

输入格式

两个正整数,N,K。

输出格式

一个正整数

(mod 100003)

ans(mod100003)，为到达第

N 级台阶的不同方式数。

输入输出样例

输入 #1复制

5 2

输出 #1复制

8

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Main main = new Main();

        main.getNumber();

    }

    public void getNumber(){

        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();

        int K = scanner.nextInt();

        int[] dp = new int[N+1];

        dp[0] = 1;

for (int i = 1; i < dp.length;i++){

            for (int j = 1; j <= K && i - j >= 0;j++){

                dp[i] = dp[i] + dp[i-j];

                dp[i] %= 100003;

            }

        }

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

    }

}