Помогите, пожалуйста, решить олимпиадную задачу

1) Начинаем с 6=й ступеньки. Здесь только один вариант добраться до 7-й ступеньки: прыгнуть на одну ступеньку. Всего 1 вариант
2) У 5-й ступеньки 2 варианта: прыгнуть на 1 ступеньку или прыгнуть на 2 ступеньки. Если прыгнуть на одну, то открывается возможность еще для одного варианта, как для 6-й. Всего 3 варианта.
3) У 4-й ступеньки есть 3 варианта: прыгнуть на 1 ступеньку или на 2 или на 3. Если на одну, то открываются еще 3 варианта, как для 5-й ступеньки, если на 2 то еще один вариант, как для 6-й. Всего 7 вариантов
4) Для 3-й ступеньки есть возможность прыгнуть либо на 1 ступеньку, либо на 2, либо на 3. Подсчитывая таким же образом находим, что всего есть 14 вариантов.
5) Для 2-й ступеньки всего оказывается 27 вариантов.
6) Для 1-й ступеньки - всего 51 вариант.
7) И наконец с земли можно прыгнуть на 1-ю, на 2-ю или на 3-ю ступеньку. Подсчитывая уже изложенным способом, находим, что в этом случае у девочки есть 95 вариантов добраться до 7-й ступеньки. Это и есть то самое число разных вариантов.
N=95
..

Пусть fi – количество вариантов на лестнице с i ступеньками.
Очевидно, что f0 = f1 = 1.
Пусть k – это максимальный прыжок.
Если первый прыжок равен 1, то на оставшихся ступеньках количество вариантов равно f(i - 1),
если 2, то f(i - 2),
если k, то f(i - k),
т.е. получаем рекуррентную формулу
f(i) = f(i - 1) + f(i - 2) + … + f(i - k).********************(1)
Если применять ее непосредственно, то многократно будут вычисляться перекрещивающиеся подзадачи, поэтому надо применить динамическое программирование, т.е. вычислить их один раз и сложить в вектор.
В нем два первых элемента единицы, а каждый следующий равен сумме предыдущих k, или всех предыдущих, если их меньше k.
Из формулы (1) имеем
f(i + 1) = f(i) + f(i - 1) + … + f(i – k + 1)****************(2)
т.е.
f(i + 1) = f(i) + f(i - 1) + … + f(i – (k - 1))***************(3)
откуда, согласно (1), получим:
f(i + 1) = f(i) + f(i) – f(i – k)
т.е.
f(i + 1) = 2 * f(i) – f(i – k)
или
f(i) = 2 * f(i - 1) – f(i – k - 1).
Разумеется, второй член вычитаем, если его индекс неотрицательный.
По этой формуле заполняем вектор, пока не дойдем до нужного нам индекса, равного заданной длине N лестницы. Значение по этому индексу и будет ответом для заданных N и k.


N=7
k=3