Как решить задачу с помощью динамического программирования?
Условие задачи:
Заяц может только разгоняться. Если он прыгнул на n кочек вперёд, то следующий прыжок не может быть меньше n. Нужно определить кол-во способов добраться до i кочки, причём последний прыжок равен k.
Вот объяснение и решение задачи от лектора, но я его не понял - https://youtu.be/P6-7bcuPs3k?t=4275
Ответы (1 шт):
Пусть c(i, k) - число способов доскакать до позиции i при условии что последний скачок не более k кочек.
Как формулируется требуемый в задаче результат в терминах функции c? Последний скачок ровно k - предыдущая кочка i - k. Заяц не тормозит, его скорость на кочке i - k не должна превосходить k (иначе заяц не может сделать последний скачок).
Нам надо вычислить c(i - k, k).
Какие есть свойства у функции c?
c(i, *) = 0, i < 0- ноль способов быть левее первой кочки (пока в этом нет смысла, позже он появится);c(1, *) = 1- на первую кочку заяц может "прибыть" на первую кочку только одним способом;c(i, k) = sum(c(i - j, j) | j in [1, k])- чтобы попасть на кочкуi, надо попасть на одну из кочек в диапазоне[i - k, i - 1]. Скорость на кочке не должна быть слишком велика, чтобы не проскочить мимоi. (Первый пункт обретает смысл: суммирование можно делать и до первой кочки).
Если вам что-то неясно в этих пунктах, задайте вопрос.
Если вам всё понятно, то вы готовы написать функцию c. Добавьте к ней кеш, получится "динамическое программирование".