Задача на динамическое программирование)

[Андрей1010]

В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек N. Заяц может одним прыжком преодолеть не более К ступенек. Для разнообразия зайчик пытается каждый раз найти новый путь к вершине лестницы. Директору любопытно, сколько различных способов есть у зайца добраться до вершины лестницы при заданных значениях K и N. Помогите директору написать программу, которая поможет вычислить это количество. Например, если K=3 и N=4, то существуют следующие маршруты: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1. Т.е. при данных значениях у зайца всего 7 различных маршрутов добраться до вершины лестницы.


Входные данные

В единственной строке входного файла INPUT.TXT записаны два натуральных числа K и N (1 ≤ K ≤ N ≤ 300). К - максимальное количество ступенек, которое может преодолеть заяц одним прыжком, N – общее число ступенек лестницы.

Выходные данные

В единственную строку выходного файла OUTPUT.TXT нужно вывести количество возможных вариантов различных маршрутов зайца на верхнюю ступеньку лестницы без ведущих нулей.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	1 3	1
2	2 7	21
3	3 10	274

Сдать задачу

[Somebody]

Википедия -> Динамическое программирование.
Что именно непонятно?

[Андрей1010]

Как решить эту задачу)

[Somebody]

Например, если K=3 и N=4, то существуют следующие маршруты: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1.

f(x) - количество способов запрыгнуть на ступеньку.
f(1) = 1 // прыгнул на ступеньку
f(2) = 1 + f(1) = 2 // прыгнул или сразу, или с первой
f(3) = 1 + f(1) + f(2) = 4 // прыгнул или сразу, или с первой, или со второй
f(4) = f(1) + f(2) + f(3) = 7 // сразу нельзя, прыгнул или с первой, или со второй, или с третьей
.......
f(n) = f(n - k) + ... + f(n - 1)

[Андрей1010]

Огромнейшее спасибо!!!