Если вы спросите любого, кто готовится к собеседованию по кодированию, каковы одни из самых сложных проблем с кодированием, ответом, скорее всего, будут проблемы с динамическим программированием. Даже когда я готовился к собеседованию в 2014 году, я боялся динамического программирования и очень хотел, чтобы я никогда не встречал его на собеседовании. Я знал теорию, лежащую в основе решений некоторых классических задач динамического программирования, таких как задача о рюкзаке и самая длинная возрастающая подпоследовательность, но если меня спрашивали о проблеме, которую я никогда раньше не видел, мне требовалось несколько дней, чтобы найти решение. Так что я вообще избежал проблем с динамическим программированием. Но в прошлом году, когда я готовился к собеседованию, я хотел столкнуться с этими проблемами лицом к лицу, я хотел столкнуться со своими страхами и действительно потратить некоторое время, чтобы стать в этом хорошим. Поэтому я решил научиться решать любую проблему динамического программирования с нуля. Я начал гуглить о динамическом программировании и прочитал много статей, но большинство из них никогда не предлагали методик решения какой-либо проблемы с нуля, вместо этого большинство из них объясняли, что такое динамическое программирование, и объясняли некоторые из наиболее распространенных проблем динамического программирования. А некоторые статьи носили слишком математический характер и больше подходят для академиков, а не для интервью. Я начал решать проблемы с Hackerrank и leetcode специально помечал проблемы динамического программирования. Многие из вас могут посочувствовать мне, что решение проблем алгоритмов с нуля без особой помощи расстраивает, и когда вы сталкиваетесь с препятствием, это также очень деморализует. Вы просто хотите прекратить это делать и пообещать себе, что, закончив собеседование, вы больше никогда не коснетесь этих проблем с алгоритмом.
Но после того, как я много боролся с несколькими проблемами динамического программирования, а также много читал о проблемах динамического программирования, я начал видеть закономерность. К моему полному удивлению, я решал проблемы, с которыми никогда раньше не сталкивался, за меньшее время (раньше на это уходило от половины до одного дня).
Возврат
Небольшая предыстория, связанная с этим. Еще в 2014 году, когда я работал в Samsung, ни с того ни с сего ко мне обратился рекрутер из Google по поводу должности инженера-программиста. Я прошел телефонное собеседование без особой подготовки, так как серьезно не искал смены работы (но эй, это Google). К моему полному удивлению, они хотели, чтобы я приехал на собеседование. Я никогда в своих мечтах не думал, что когда-нибудь пройду интервью в Google, не говоря уже о том, чтобы работать на них. Я действительно хотел хорошо подготовиться и хорошенько постараться. Я искал в Интернете советы по подготовке к интервью в Google, что читать, какие раунды будут там проходить, и наткнулся на эту удивительную книгу Стива С. Скиенны под названием Руководство по разработке алгоритмов. До этого времени моей подготовки к собеседованию было недостаточно для этих крупных компаний, особенно циклов программирования (вот почему я работал в Samsung). Я сконцентрировался в основном на основах информатики и решил несколько задач на собеседовании Взломать код. Я думал, что этого достаточно (вздыхает). Эта книга открыла мне глаза на мир разработки алгоритмов, о существовании которого я даже не подозревал. Он познакомил меня с некоторыми методами разработки алгоритмов, такими как поиск с возвратом, поиск в глубину, поиск в ширину, и помог мне понять, как применять эти методы. Я не смог пройти собеседование в Google, и мне пришлось некоторое время оставаться в Samsung, но то, что я узнал из этой книги, осталось со мной, и это заставило меня по-другому взглянуть на эти проблемы алгоритмов. Одной из техник, которые меня увлекли, были рекурсия и отслеживание с возвратом. В этой книге автор дал общую основу для решения задач исчерпывающего поиска. Я был удивлен тем, сколько проблем, которые задают на собеседовании, можно решить с помощью этой техники. Я попытался применить обратное отслеживание почти ко всем проблемам, по крайней мере, это помогло мне получить наивное решение проблем, например, перестановки, комбинации, поиск в глубину и т. Д.
Мышление сверху вниз
При решении задач динамического программирования, хотя я понимал лежащие в основе концепции, такие как оптимальная подструктура и перекрывающиеся подзадачи, я не знал, как применить их к проблемам, которых я никогда раньше не видел. Я всегда пытался придумать рекурсивную формулу и как-то использовать ее, чтобы придумать восходящее решение. Я всегда думал, что динамическое программирование должно быть заполнением таблиц снизу вверх. Но поскольку мне было комфортно с рекурсией и отслеживанием с возвратом, я вскоре понял, что почти все проблемы динамического программирования также могут быть решены с помощью рекурсии и отслеживания с возвратом. Это не самые оптимальные решения, но я понял, что думать «сверху вниз», чтобы находить решения, было намного проще и казалось очень естественным. Но мне все еще было трудно осмыслить восходящие решения.
Воспоминание
Я всегда думал, что динамическое программирование заполняет таблицы результатами снизу вверх и использует их для вычисления других результатов, потому что это то, что я читал в учебниках как во время учебы в бакалавриате, так и во время учебы в магистратуре. Я слышал об этом слове «мемоизация», но мне никогда не хотелось понимать, что именно оно означает. Итак, пока я решал задачи DP, у меня появилась возможность пересмотреть эту концепцию. Вскоре я понял, что Мемоизация - это не что иное, как вариант динамического программирования. В мемоизации все, что вы делаете, - это рекурсивная реализация решения и кэширование результатов в структуре данных, обычно в массиве или хэш-карте, используя значения входных параметров в качестве ключа. Если результат присутствует, мы вернем это кешированное значение или воспользуемся рекурсией для вычисления результатов. Это было ключевым осознанием, изменившим мой взгляд на проблемы DP. Я смог использовать рекурсию, отслеживание с возвратом и мемоизацию для решения почти всех проблем DP. В Leetcode и Hackerrank хорошо то, что они позволяют сравнивать время выполнения вашего решения с другими решениями на том же языке программирования, и я был удивлен, увидев, что мои решения с использованием мемоизации работают хорошо, они не были самыми быстрыми решениями, но я могу говорят, что они были лучше, чем 70 процентов решений. Я начал получать удовольствие от всего процесса использования рекурсии для разработки решений и использования кеша для хранения и получения результатов. Для кеша я изначально использовал HashMap, и если было более одного параметра, я использовал для создания строки, разделенной запятыми, с использованием значений параметров и использовал это как ключ к кешу. Но я понял, что использование массива для кеширования намного быстрее, даже несмотря на то, что для этого требуется больше памяти. 1D массив, если есть один параметр или 2D массив, если есть 2 параметра и так далее.
Восходящее решение
Теперь задача заключалась в том, чтобы понять, как использовать эти знания, чтобы прийти к восходящему решению. Внимательно изучив как нисходящее, так и восходящее решение для нескольких проблем, я выяснил, что простой четырехэтапный процесс преобразования нисходящего решения в восходящее решение.
- Инициализировать массив. Размер массива зависит от количества параметров, определяющих состояние.
- Для каждого параметра используйте цикл for, чтобы перебрать все возможные значения параметра.
- В рекурсивном решении, если значение параметра уменьшается при рекурсивном вызове функции, мы перебираем значение параметра в порядке возрастания. Если значение увеличивается в рекурсивном вызове, мы перебираем значение в порядке убывания.
- Внутри цикла for примените рекурсивную формулу, но вместо вызова рекурсивной функции используйте результаты из кеша.
Восходящее решение работает намного лучше, чем рекурсивное решение, поскольку рекурсия вызывает много накладных расходов. Я смог протестировать этот пошаговый подход для решения новых проблем DP с нуля, и он отлично сработал. Я смог решить новые задачи менее чем за час. Я собрал много разных задач DP из разных источников, чтобы протестировать этот подход, некоторые из них - leetcode, codechef, hackerrank и geek for geeks. Подход на удивление хорошо работал с эффективными решениями.
Овладейте искусством динамического программирования
Я подумал о том, чтобы поместить то, что я изучил до сих пор, в курс, чтобы он мог помочь моим друзьям и всем, кто может извлечь выгоду из этого подхода, с легкостью попрактиковаться в решении все большего и большего числа задач динамического программирования. Вот почему я создал этот курс по Udemy под названием «Овладейте искусством динамического программирования».
(Вы можете перейти по этой ссылке, чтобы купить курс со скидкой 50%).
В нем 4,5 часа курсовых видео. Обсуждаемые темы:
- Рекурсия
- Возврат
- Введение в динамическое программирование
- Проблемы оптимизации
- Пошаговый подход к решению задач DP
- Одномерное динамическое программирование
- Двумерное динамическое программирование
Подробно объясняются 15 важных проблем динамического программирования. Эти задачи выбраны для того, чтобы объяснить все аспекты динамического программирования. Кроме того, я включил подробный анализ временной и пространственной сложности для каждого из решений динамического программирования, описанных в этом курсе. Надеюсь, это тебе поможет.
