Кенгуру возраста К может прыгать вперед на любое из расстояний от 1 до К. Ей нужно,двигаясь по прямой попасть из точки 0 в точку M.Сколькими способами кенгуру может это сделать. Длины прыжков и расстояние, на котороедолжна попасть кенгуру, выражаются целыми числами.Пример:Ввод (K, М):2 3Вывод:3

Предыдущий
вопрос Следующий
вопрос

Для решения этой задачи можно воспользоваться динамическим программированием.

Создадим массив dp, где dp[i] будет обозначать количество способов, которыми кенгуру может попасть в точку i. Изначально заполним массив нулями, кроме dp[0] = 1.

Затем заполним массив dp по следующему правилу: для каждой точки i от 1 до M, будем перебирать все возможные длины прыжков j от 1 до K и суммировать количество способов dp[i-j].

В конце получим результат в dp[M].

Пример:
Ввод (K, M): 2 3
dp = [1, 1, 0, 0]

При i = 1:
dp[1] = dp[1-1] = dp[0] = 1

При i = 2:
dp[2] = dp[2-1] + dp[2-2] = dp[1] + dp[0] = 1 + 1 = 2

При i = 3:
dp[3] = dp[3-1] + dp[3-2] = dp[2] + dp[1] = 2 + 1 = 3

Ответ: 3

Таким образом, кенгуру может попасть в точку 3 тремя способами.