Задача про кузнечиков

Даны n последовательных столбиков. Кузнечик находится на первом столбе, умеет прыгать на 1,2,...,k столбиков. Найти количество вариантов, которым он может допрыгать до n-го столба.
Я знаю что решается динамическим программированием, пытался сам в нём разобрать, но не получилось.
Мне нужен код на Pascal или C++, желательно с подробным объяснением.

0

Да over9000. Захотел - прыгнул вперед, захотел - назад.

0

кузнечик умеет прыгать на 1,2,...,k столбиков вперед

0

будем обозначать к-во вариантов с позиции, когда осталось Р столбиков f(p). Тогда
f(p)= f(p-1) + f(p-2) + ... + f(p-k),
причём f(0)=1, f(число меньше 0)=0.

И если впадло писать код и n маленькое - пошла рекурсия,
если хочешь нормально - создаём массив размером n, в котором будут храниться f(p) для р=1..n
И пошла индукция, р увеличивем от 1 до n, на каждом шаге сохраняем f(p) в массив. Этот алгоритм требует n раз взять сумму k (по крайней мере не более чем k) элементов, но подлость в том, что такой алгоритм не оптимален.

Ведь на самом деле
f(p) = f(p-1) + f(p-2) + ... + f(p-k) = f(p-1) + f(p-1) - f(p-k-1) = 2*f(p-1) - f(p-k-1)
И тогда для нохождения каждого нового элемента нам нужно 2 операции сложения вместо к операций сложения. Можно заюзать операцию умножения и операцию сложения, здесь вопрос в том, что легче - (операция умножения) или (операция сложения плюс дополнительное обращение к ячейке памяти). Я начинающий программист, на такой вопрос ответа, к сожалению, не знаю.

Итого имеем 2n операций сложения + 3n обращений к ячейкам, либо n операций сложения, столько же операций умножения и 2n обращений к ячейкам. Довольно похоже на оптимальныое решение.

1

Если честно, ничего не прояснило

Добавлено через 34 минуты
Я понял, что если прыгать до k столбика то это сумма всех предыдущих вариантов добраться, а до k+1 сколько?

0