Когда дело доходит до технических собеседований, наиболее часто запрашиваемой темой является DP (динамическое программирование), и именно эта тема больше всего пугает студентов.
Вы слышали об этом высказывании?
Тот, кто забывает прошлое, склонен его повторять!
Аналогично обстоит дело с динамическим программированием. Главным ключом в решении задач ДП является способ решения.
Например, я заставлю вас пройти через все шаги и методы решения проблемы DP. От подхода «снизу вверх» к подходу «сверху вниз».
От запоминания до табулирования и оптимизации пространства.
Главное условие перед погружением в динамическое программирование — это рекурсия. Это основной строительный блок решений DP.
Без рекурсии не решить ни один из вопросов ДП.
Как определить проблему ДП?
Всякий раз, когда мы запускаем программу, разрушая отношение рекурсии любого решения вопроса, мы можем обнаружить некоторые повторяющиеся случаи. В этих случаях мы должны убедиться, что наилучшим подходом к решению вопроса является использование DP.
Я буду решать задачу Фибоначчи с помощью рекурсии, а затем мы будем применять динамическое программирование для ее оптимального решения.
Вопрос: Найдите n-е число Фибоначчи.
Ответ:
- Использование рекурсии
2. Использование метода мемоизации.
ссылка на вопрос: https://leetcode.com/problems/fibonacci-number/
В следующей статье мы обсудим еще некоторые вопросы и другие подходы, такие как табуляция и оптимизация пространства.
А пока вы можете попробовать сами.
Приятного обучения и изучения.
Дхрув Гупта 💡
