Чем 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.