re:re:actable
Урок 063 минуты чтения

Чем greedy отличается от dynamic programming?

На этой странице
Кратко

Greedy делает локально лучший выбор и не пересматривает его. Dynamic Programming хранит ответы подзадач и рассматривает варианты. Greedy быстрее и проще, но работает только если локальный выбор гарантирует глобальный оптимум.

Вопрос

Чем greedy отличается от dynamic programming и как понять, что жадный подход корректен?

Greedy example

Задача: максимум активностей без пересечений.

Идея: сортируем по времени окончания и берем первую совместимую.

type Interval = [number, number]
 
function maxNonOverlapping(intervals: Interval[]): number {
  const sorted = [...intervals].sort((a, b) => a[1] - b[1])
 
  let count = 0
  let lastEnd = -Infinity
 
  for (const [start, end] of sorted) {
    if (start >= lastEnd) {
      count++
      lastEnd = end
    }
  }
 
  return count
}

Почему это корректно: интервал, который заканчивается раньше всех, оставляет больше всего места для остальных. Если в каком-то оптимальном ответе первым стоит другой интервал, его можно заменить на наш - он заканчивается не позже, значит ничему не мешает. Такое рассуждение называется exchange argument (обменный аргумент).

Когда greedy ошибается: размен монет

Задача: набрать сумму минимальным числом монет.

С монетами [1, 5, 10, 25] жадный способ "бери самую крупную монету, которая помещается" работает. А с монетами [1, 3, 4] и суммой 6:

greedy: 4 + 1 + 1 = 3 монеты
лучше:  3 + 3     = 2 монеты

Первый выбор (4) казался лучшим, но испортил итог. DP перебирает все варианты для каждой суммы:

function coinChange(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(Infinity)
  dp[0] = 0 // сумму 0 набираем без монет
 
  for (let sum = 1; sum <= amount; sum++) {
    for (const coin of coins) {
      if (coin <= sum) dp[sum] = Math.min(dp[sum], dp[sum - coin] + 1)
    }
  }
 
  return dp[amount] === Infinity ? -1 : dp[amount]
}

Для [1, 3, 4]: dp = [0, 1, 2, 1, 1, 2, 2], ответ dp[6] = 2.

DP example

Knapsack нельзя надежно решить greedy по value/weight, потому что локально лучший предмет может испортить глобальный ответ.

Там нужны варианты:

take item
skip item

Как отличить?

Greedy подходит, если:

  • есть доказуемое greedy choice property;
  • локальный выбор не мешает будущему;
  • можно обменным аргументом доказать оптимальность.

DP подходит, если:

  • есть повторяющиеся подзадачи;
  • нужно сравнивать варианты;
  • состояние можно описать параметрами.

Что отвечать на собеседовании?

Greedy выбирает лучший вариант прямо сейчас и не хранит все подзадачи. DP систематически перебирает состояния и сохраняет результаты. Greedy обычно быстрее, но требует доказательства, что локальный выбор ведет к глобальному оптимуму. Если такого свойства нет, часто нужен DP.

Что важно помнить: частые ошибки

  • Использовать greedy без доказательства.
  • Решать 0/1 knapsack greedy.
  • Называть любое быстрое решение greedy.
  • Не объяснять, почему локальный выбор безопасен.
  • Использовать DP там, где достаточно greedy.

Мини-шпаргалка

  • Greedy = локальный выбор.
  • DP = состояния и варианты.
  • Greedy needs proof.
  • DP needs state/transition.
  • Greedy часто O(n log n) из-за сортировки.
  • Knapsack 0/1 обычно DP.

Документация

Wikipedia: Greedy algorithm.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам