Question

Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть вперед на расстояние от 1 до K столбиков, считая от текущего. Требуется найти количество способов, которыми Кузнечик может добраться до столбика с номером N . Учитывайте, что Кузнечик не может прыгать назад. Входные данные Входная строка содержит натуральные числа N и K , разделённые пробелом. Гарантируется, что 1 ≤ N , K ≤ 32 . Выходные данные Программа должна вывести одно число: количество способов, которыми Кузнечик может добраться до столбика с номером N . Примеры Входные данные 5 4 Выходные данные 8 Программа должна быть на питоне

Answer 1

n=int(input())

k=int(input())

a=[1]

for i in range(1,n):

 for j in range(i-1,i-k-1,-1):

   if j<0 :

     break

   a.append(0)

   a[i]+=a[j]

print(a[n-1])