Олимпиадная задача №11 Зайчик

[NiceEnd]

Здравствуйте, прошу помочь решить задачу:

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

Входные данные: Ввести с клавиатуры два натуральных числа K и N (1<=K<=N<=300). K - максимальное количество ступенек, которое может преодолеть заяц одним прыжком, N - общее число ступенек.

Выходные данные: Нужно вывести S - количество возможных вариантов различных маршрутов зайца.

Примеры:
K=1 N=3 S=1
K=2 N=7 S=21
K=3 N=10 S=274

Сама задача мне ясна, но не могу разбить N на сумму всех возможных натуральных чисел. Извиняюсь, если данная задача уже есть на форуме.

[Serge_Bliznykov]

угу. была. и даже алгоритм решения предложен (на основе т.н. "динамического программирования")

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