Мы Competitive Programming London, мы встречаемся раз в неделю, чтобы попрактиковаться в некоторых алгоритмических задачах из Codeforces, Hackerrank, Leetcode и других задачах. Общий формат наших встреч — работать над несколькими проблемами в парах, а затем обсуждать решения друг друга в целом ближе к концу.

на этой встрече мы начали углубляться в проблемы динамического программирования.

Динамическое программирование (DP) заключается в поиске некоторой работы (обычно рекурсивной), которая будет повторяться несколько раз без необходимости, и поэтому было бы лучше сохранить эти подзадачи с течением времени.

Проблемы с DP довольно распространены в соревновательных соревнованиях. DP часто может казаться волшебным, но с практикой он начинает обретать смысл. Мы начали смотреть первое видео в сериале Эррихто, которое состояло из сплошной экспоненты. Следующие несколько абзацев подведут итог видео.

К каким программам применимы задачи DP?

  1. Комбинаторика (сосчитать что-либо, количество способов)
  2. Минимизировать или максимизировать значение
  3. Да, без вопросов

Для 2 и 3 всегда полезно, если жадный подход сработает, прежде чем переходить к DP.

Существует 2 метода применения решений DP к заданной проблеме: итеративный и рекурсивный. Оба они очень похожи, но давайте рассмотрим некоторые различия:

Некоторые ведущие программисты, включая Эррихто, похоже, предпочитают итеративные решения DP.

Проблемы решены

Вот задачи, которые мы решили на сессии:

Мы продолжим с более продвинутыми. Проблемы с ДП в следующий раз.

Если вы находитесь в Лондоне, я надеюсь увидеть вас на следующем мероприятии :). Хотите присоединиться к нашей слабой группе, чтобы обсудить подобные проблемы? Напишите мне в twitter или linkedin, чтобы присоединиться