Условие

У одного из студентов в комнате живёт кузнечик, который очень любит прыгать по клетчатой одномерной доске. Длина доски — N клеток. К его сожалению, он умеет прыгать только на 1, 2, …, k клеток вперёд.

Однажды студентам стало интересно, сколькими способами кузнечик может допрыгать из первой клетки до последней. Помогите им ответить на этот вопрос.

Примеры

Ввод: 8 2 Вывод: 21

Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun countWays(n: Int, k: Int): Int {
    val dp = IntArray(n + 1)
    dp[1] = 1 // Единственный способ стоять на первой клетке
    
    for (i in 2..n) {
        for (j in 1..k) {
            if (i - j >= 1) {
                dp[i] += dp[i - j] // Считаем количество способов попасть в клетку i
            }
        }
    }
    return dp[n]
}

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))
    val (n, k) = reader.readLine().split(" ").map(String::toInt)
    writer.write(countWays(n, k).toString())
    writer.newLine()
    writer.flush()
    reader.close()
    writer.close()
}