У чому відмінність DP від жадібного алгоритму?

АлгоритмиJunior~3 хв читання

У чому відмінність DP від жадібного алгоритму?

Коротка відповідь

DP (динамічне програмування) системно перебирає простір станів і повторно використовує результати підзадач. Дає гарантовано оптимальне рішення за наявності оптимальної підструктури; зазвичай дорожче за часом/пам'яттю, але універсальніше.
Жадібний алгоритм робить локально найкращий вибір на кожному кроці без відкату. Швидкий і простий, але потребує властивості жадібного вибору; без неї може дати неоптимум.

Динамічне програмування (DP): розбиваємо задачу на підзадачі, розв'язуємо їх один раз, зберігаємо результат і комбінуємо відповіді. Основа - оптимальна підструктура (оптимум будується з оптимумів підзадач) і перетинні підзадачі.

Жадібний алгоритм: обираємо на кожному кроці локально найкращий варіант за деяким критерієм, не повертаючись назад. Коректність можлива, коли виконується властивість жадібного вибору: локальний вибір можна «обміняти» на частину оптимального рішення без втрати якості.

Ключові відмінності

Гарантія оптимальності: DP - так (за коректної моделі), жадібний - лише якщо доведено властивість жадібного вибору.
Стратегія: DP будує і повторно використовує таблицю/кеш станів (bottom-up/мемоізація); жадібний приймає послідовність локальних рішень без кешу і відкатів.
Пам'ять: DP зберігає таблиці станів (часто O(кількість станів)); жадібний майже завжди O(1)-O(n).
Час: DP зазвичай поліноміальний за розміром простору станів; жадібний - часто O(n log n) або O(n).
Доведення коректності: DP - через рекуренту та індукцію/принцип Беллмана; жадібний - через обмінний аргумент або доведення властивості жадібного вибору.
Гнучкість: DP застосовний ширше; жадібний значно простіший і швидший там, де застосовний.

Як зрозуміти, що застосовувати

Ознаки DP: підзадачі повторюються; рішення описується через невеликий «стан»; легко записати рекуренту; потрібна точна гарантія оптимуму.
Ознаки жадібного: можна сформулювати природний локальний критерій (сортування за ним + однопрохідний відбір); вдається побудувати обмінний аргумент; не знаходиться контрприклад.

Приклад 1: розмін монет (мінімум монет)

Монети {1, 3, 4}, сума 6. Жадібний візьме 4 -> залишок 2 -> 1+1 = 3 монети, що неоптимально. Оптимум - 3+3 = 2 монети. DP завжди знаходить оптимум (для цієї постановки).

// Жадібний розмін монет (може дати неоптимум)
function coinChangeGreedy(coins, amount) {
  coins = [...coins].sort((a, b) => b - a);
  let count = 0;
  for (const c of coins) {
    const use = Math.floor(amount / c);
    count += use;
    amount -= use * c;
  }
  return amount === 0 ? count : Infinity;
}

console.log(coinChangeGreedy([1, 3, 4], 6)); // 3 (4 + 1 + 1) - неоптимально; оптимум 2 (3 + 3)

// DP: мінімум монет (табуляція)
function coinChangeDP(coins, amount) {
  const INF = 1e9;
  const dp = new Array(amount + 1).fill(INF);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (a - c >= 0) dp[a] = Math.min(dp[a], dp[a - c] + 1);
    }
  }
  return dp[amount] === INF ? -1 : dp[amount];
}

console.log(coinChangeDP([1, 3, 4], 6)); // 2 (3 + 3)

Приклад 2: відбір непересічних інтервалів (жадібний працює)

Класична задача: обрати максимум непересічних інтервалів. Жадібний критерій - сортувати за часом завершення і брати кожен наступний непересічний. Доведення через обмінний аргумент.

function selectMaxActivities(intervals) {
  intervals.sort((a, b) => a.end - b.end);
  const result = [];
  let lastEnd = -Infinity;
  for (const it of intervals) {
    if (it.start >= lastEnd) {
      result.push(it);
      lastEnd = it.end;
    }
  }
  return result;
}

const intervals = [
  { start: 1, end: 4 },
  { start: 3, end: 5 },
  { start: 0, end: 6 },
  { start: 5, end: 7 },
  { start: 8, end: 9 },
];

console.log(selectMaxActivities(intervals)); // жадібний дає оптимум

Шпаргалка для співбесіди

Сформулюйте критерій оптимальності та стан (які параметри описують підзадачу).
Перевірте оптимальну підструктуру і перетинність підзадач -> якщо так, сміливо пропонуйте DP (top-down з мемоізацією або bottom-up).
Спробуйте жадібний критерій: відсортуйте, запропонуйте локальний вибір, знайдіть/спростуйте контрприклад. Якщо контрприкладів немає і є обмінний аргумент - обирайте жадібний.
Оцініть складність за часом і пам'яттю; вкажіть, чому метод гарантує оптимальність (або коли може не спрацювати).

Зведення відмінностей

Критерій	DP	Жадібний
Ідея	Перебір станів із повторним використанням результатів	Локальний найкращий вибір без відкату
Умови коректності	Оптимальна підструктура, перетинні підзадачі	Властивість жадібного вибору (обмінний аргумент)
Оптимальність рішення	Гарантована (за коректної моделі)	Не гарантована без доведення властивості
Пам'ять	Вища (таблиці станів)	Нижча (часто O(1)-O(n))
Типова складність	O(кількість станів × кількість переходів)	O(n log n) або O(n)
Приклад	Мінімум монет, рюкзак, LIS	Відбір інтервалів, Хаффман, задачі на мінімальні вартості за канонічних систем

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.

У чому відмінність DP від жадібного алгоритму?