Мы Competitive Programming London, мы встречаемся раз в неделю, чтобы попрактиковаться в некоторых алгоритмических задачах из Codeforces, Hackerrank, Leetcode и других задачах. Общий формат наших встреч — работать над несколькими проблемами в парах, а затем обсуждать решения друг друга в целом ближе к концу.
на этой встрече мы начали углубляться в проблемы динамического программирования.
Динамическое программирование (DP) заключается в поиске некоторой работы (обычно рекурсивной), которая будет повторяться несколько раз без необходимости, и поэтому было бы лучше сохранить эти подзадачи с течением времени.
Проблемы с DP довольно распространены в соревновательных соревнованиях. DP часто может казаться волшебным, но с практикой он начинает обретать смысл. Мы начали смотреть первое видео в сериале Эррихто, которое состояло из сплошной экспоненты. Следующие несколько абзацев подведут итог видео.
К каким программам применимы задачи DP?
- Комбинаторика (сосчитать что-либо, количество способов)
- Минимизировать или максимизировать значение
- Да, без вопросов
Для 2 и 3 всегда полезно, если жадный подход сработает, прежде чем переходить к DP.
Существует 2 метода применения решений DP к заданной проблеме: итеративный и рекурсивный. Оба они очень похожи, но давайте рассмотрим некоторые различия:
Некоторые ведущие программисты, включая Эррихто, похоже, предпочитают итеративные решения DP.
Проблемы решены
Вот задачи, которые мы решили на сессии:
- Фебаноччи (из видео)
- Лестничная задача (из видео)
- Лестничная задача модифицирована (из видео)
- Проблема минимального пути сетки (из видео)
- Умная девочка
- Илья и запросы
Мы продолжим с более продвинутыми. Проблемы с ДП в следующий раз.
Если вы находитесь в Лондоне, я надеюсь увидеть вас на следующем мероприятии :). Хотите присоединиться к нашей слабой группе, чтобы обсудить подобные проблемы? Напишите мне в twitter или linkedin, чтобы присоединиться