Предлагаю потренироваться решать задачи на динамическое программирование на одной из классических задач. Читаем условие:
Как определить, что задача на динамическое программирование? Кроме того, что на сайте указан раздел, из которого задача, метод динамического программирования чаще всего помогает отвечать на вопросы "сколько способов?" и "какой способ оптимальный?". Да, есть ещё варианты, например, зная количество способов и первое число в "решении" можно найти k-ое по счёту решение.
Итак, в этой задаче как раз надо посчитать количество способов подняться на лестницу.
При решении методом динамического программирования надо определить три вещи: что является состоянием, переходы между состояниями и база динамики.
Состояние - это параметры, которыми характеризуется подзадача. Это может быть:
- координаты точки на карте, если мы ищем путь в лабиринте;
- левая и правая граница подстроки, если мы находим все подстроки палиндромы;
- длины префиксов двух строк, если мы ищем расстояние Левенштейна между ними.
Чаще всего состояние можно понять из условия задачи. И лишь иногда к тому, что дано приходится добавлять дополнительный параметр.
В нашем случае надо найти количество способов добраться до ступеньки n, а подзадачами будут - найти количество способов добраться до ступеньки i (для всех i от 0 до n). Значит в качестве состояния можно взять номер ступеньки.
Второй элемент - это переходы между состояниями. Их легко понять, если ответить на вопрос "как мы сюда можем попасть?". Например, если мы стоим на ступеньке i, то как мы могли на неё попасть? Очевидно, что с любой ступеньки с номерами i - k, i - k + 1, ..., i - 1 (если такие есть, то есть не меньше нуля).
Зная состояния, мы понимаем, как хранить данные (одномерный массив), зная переходы, мы понимаем, как заполнять нашу структуру данных (слева направо, так как для больших номеров состояния нужны значения меньших состояний).
Осталось определиться с базой динамики. Часто это тривиальные или даже вырожденные состояния, для которых мы уже знаем ответ. База динамики нужна для того, чтобы инициализировать стартовые значения, опираясь на которые можно будет посчитать ответ для всех подзадач, используя переходы между состояниями.
У нас вырожденным случаем является нулевая ступенька (можно было бы взять и тривиальное состояние - первую ступеньку) и для неё ответ 1. Так как зайчик уже там и значит попал туда одним единственным способом.
После такого разбора написать решение не составит труда:
Заводим наш массив для динамического программирования и задаём базу динамики:
А теперь надо для всех возможных (и интересных нам) состояний посчитать ответ. Для этого для каждого состояния от 1 до n найдём сумму способов попасть на ступеньки с номерами от i - k до i - 1. Это работает, потому что на ступеньку i мы можем попасть следующим образом: добраться любым возможным способом до ступеньки с номером от i - k до i - 1 и затем одним прыжком на ступеньку i. Почему именно одним прыжком? Чтобы избежать повторного подсчёта способов, если зайчик сделает прыжок короче, то он окажется на какой-то из ступенек с номерами от i - k + 1 до i - 1, а значит этот способ уже был нами учён:
Напомню сигнатуру функции sum, которая находит сумму слайса массива:
sum(iterable, /, start=0)
Осталось вывести ответ:
Эта задача имеет достаточно большую сложность, потому что ответ не помещается в стандартные типа данных на языке C++, и приходится реализовывать "длинное" сложение. На Python таких проблем не возникает.
В качестве более сложного примера задачи на динамическое программирование можете посмотреть на Задача 708. Хомяки и кролики. К тому же, это был один из первых разборов на этом канале, поэтому там меньше слов, больше кода.
Предыдущий выпуск: Задача 41. Сортировка подсчетом
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.