LeetCode #70, JavaScript
Сегодня я начинаю изучать динамическое программирование и работать над задачей LeetCode Восхождение по лестнице.
Концепция проста, нам будет дана лестница из n ступенек. Мы можем делать один или два шага за раз, и нам нужно вернуть количество уникальных способов, которыми мы можем подняться по лестнице.
Итак, если бы у нас была лестница высотой всего в две ступени, мы могли бы подняться по ней двумя способами:
каждый шаг по отдельности или оба шага сразу. Наше возвращаемое значение здесь будет 2.
Кто знает, сколько подходов может сработать для этого. Я мог видеть, что это решаемо с использованием структуры перестановки или даже с некоторыми трудоемкими вложенными итеративными усилиями.
Но моя конечная цель всегда одна и та же с проблемами Leetcode — понять простейшую, самую элементарную природу того, что передо мной. И после нескольких тупиковых попыток я понял тенденцию увеличения числа решений от шага 0…
1 шаг = 1
2 шага = 2
3 шага = 3
4 шага = 5
5 шагов = 8…
Сюрприз!… это последовательность Фибоначчи
И это означает, что решение для каждого шага — это просто количество решений для двух предыдущих шагов. (шаг 3 имеет количество решений шага 1 + шага 2)
Итак, наши подзадачи — это решения для 1 шага и 2 шагов. Отсюда мы можем получить количество решений для любого последующего шага.
Так почему бы просто не реализовать функцию Фибоначчи и покончить с этим.
В конце концов, это просто и позволяет достичь того, что мы собираемся сделать. И технически это работает. Однако со всеми накладными расходами, связанными с рекурсией, вы, вероятно, получите тайм-аут от Leetcode.
В этом сценарии работает базовый итеративный подход:
Но одной из целей этой задачи является практика динамического программирования или запоминания.
Я слышал, что эти термины упоминаются почти взаимозаменяемо, но, работая над этой проблемой, я действительно хотел понять их различия.
Запоминание
Мемоизация — это метод, при котором мы сохраняем результаты предыдущих вычислений для использования в будущем.
Итак, давайте изменим рекурсивный подход, описанный выше, чтобы сделать это.
Итак, теперь мы будем добавлять в памятку о возврате каждого рекурсивного вызова.
Стоит отметить, что при решении задачи о подъеме по лестнице с помощью рекурсии, как я об этом думаю, мы на самом деле спускаемся с верхней ступеньки.
В строке 5, когда будет сделан первый рекурсивный вызов ClimbStairs, мы будем продолжать открывать новые контексты выполнения до тех пор, пока не вернем одно из наших значений из исходного мемо ([0, 1]). Затем эти контексты начнут закрываться и создавать нашу памятку.
С этого момента мы можем сократить значительное количество рекурсивных вызовов функций, обращаясь к этим ранее сохраненным значениям.
Динамическое программирование
Теперь, насколько я читал, динамическое программирование — это когда кто-то решает рекурсивную задачу итеративно, используя либо табуляцию, либо мемоизацию. Стремясь сделать это кратким, я не буду слишком глубоко погружаться в различия. Достаточно сказать, что мемоизация (как видно из приведенного выше примера) в конечном итоге использует нисходящий подход, работая сверху вниз по направлению к подзадачам.
С другой стороны, табулирование — это восходящий подход, при котором сначала решаются подзадачи, а затем они используются для построения окончательного решения.
Теперь мы начинаем с этого «нижнего шага» и попутно кэшируем вычисления, уменьшая рабочую нагрузку и приближаясь к нашему целевому шагу.
Скоростные пробные версии
Что быстрее — рекурсивное запоминание или подход динамического программирования с использованием табуляции?
Чтобы ответить на этот вопрос, я настроил несколько вызовов performance.now() для тактирования каждой функции с особенно значительными аргументами. Максимальное значение, которое я мог передать в рекурсивную функцию, было ~7000 без превышения максимального стека вызовов, так что это был мой ограничивающий фактор.
При таком размере входных данных динамический подход мог выполняться примерно в 5,6 раза быстрее, чем рекурсивная (запоминаемая) версия.
Этого более чем достаточно, чтобы убедить меня, что мне нужно посвятить значительно больше времени тому, чтобы сделать динамическое программирование знакомой техникой в моем наборе навыков.
Дополнительные материалы на PlainEnglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter и LinkedIn. Присоединяйтесь к нашему сообществу Discord.
