Задача про зайчика

[Gts]

Цитата:

В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек 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 различных маршрутов добраться до вершины лестницы.

Цитата:

К - максимальное количество ступенек, которое может преодолеть заяц одним прыжком, N – общее число ступенек лестницы.
$1 \leqslant K \leqslant N \leqslant 300$

Моё решение такое: представим, что лесенка - это у нас число в системе счисления по основанию $K+1$. Каждая ступенька - это разряд нашего числа. Мы будем перебирать все комбинации из диапазона $[0; m)$, где $m = (K+1)^N$ и отбирать те варианты, где сумма разрядов будет равна $N$ и остальные разряды будут равны нулю или разрядов для суммирования больше не будет. Варианты, где в середине последовательности идут нули или где сумма уже превысила $N$, но есть ещё разряды, не рассматриваем.

Проблема этого решения, что тут слишком большая алгоритмическая сложность. Поэтому прошу дать идею в какую сторону ещё можно посмотреть. Так сказать немного подтолкнуть, не давая значительного куска решения.

[SomePupil]

Gts в сообщении #1248361 писал(а):

Поэтому прошу дать идею в какую сторону ещё можно посмотреть.

Надо познакомиться с динамическим программированием.

[guryev]

Это упорядоченные разбиения числа на слагаемые. Гуглите выделенное.

Кстати, здесь это тоже обсуждалось.