Динамическое программирование и жадные алгоритмы

Динамическое программирование и жадные алгоритмы

Технический фундамент выбора стратегии

Перед кодом полезно формализовать задачу:

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

Без этого DP превращается в "магическую таблицу", а жадный алгоритм в непроверенную эвристику.

Почему эти подходы важны

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

Ключевой момент: жадный алгоритм принимает локально лучшее решение "здесь и сейчас", а DP запоминает результаты подзадач и строит глобально оптимальное решение.

Проверь себя: почему локально выгодный шаг не всегда дает лучший финальный результат?

Жадный подход простыми словами

Жадный алгоритм на каждом шаге выбирает лучший доступный вариант по текущему критерию.

Пример: размен суммы монетами, когда номиналы удачные (например, 1, 5, 10, 25).

function greedyCoins(amount) {
  const coins = [25, 10, 5, 1];
  let count = 0;

  for (const coin of coins) {
    const used = Math.floor(amount / coin);
    count += used;
    amount -= used * coin;
  }

  return count;
}

Смотри, что важно: жадность работает быстро, но не всегда дает оптимум для любых наборов правил.

Смотри, что важно: пример, где жадность не оптимальна (как в задачах). Для target = 6 и packs = [4, 3, 1]:

  • жадный выбор: 4 + 1 + 1 -> 3 пакета;
  • оптимум: 3 + 3 -> 2 пакета.

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

Динамическое программирование

DP использует идею: "если подзадача повторяется, не считай ее заново".

Новый термин: мемоизация - кеширование результата функции для уже встречавшихся входов.

function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];

  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

console.log(fib(10)); // 55

Дополнительный пример: DP в итеративной форме (tabulation) для Fibonacci.

function fibTab(n) {
  if (n <= 1) return n;
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

Смотри, что важно: DP часто выглядит как формула перехода для dp[i]. Пример "ступеньки" (можно идти на 1 или 2):

function stairsWays(n) {
  const dp = Array(n + 1).fill(0);
  dp[0] = 1;
  dp[1] = 1;
  for (let i = 2; i <= n; i += 1) dp[i] = dp[i - 1] + dp[i - 2];
  return dp[n];
}

Еще один частый паттерн: "минимум пакетов/монет для точной суммы" (DP по сумме).

function minPacks(target, packs) {
  const dp = Array(target + 1).fill(Infinity);
  dp[0] = 0;

  for (let sum = 1; sum <= target; sum += 1) {
    for (const p of packs) {
      if (sum - p >= 0) dp[sum] = Math.min(dp[sum], dp[sum - p] + 1);
    }
  }

  return dp[target];
}

Еще один распространенный DP: минимум стоимости пути в сетке (идем только вправо и вниз).

// dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

И еще один: максимум суммы без выбора соседних элементов (классический "house robber").

function maxSumNoAdjacent(arr) {
  let prev2 = 0;
  let prev1 = 0;
  for (const x of arr) {
    const cur = Math.max(prev1, prev2 + x);
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}

В задачах на строки (например, расстояние Левенштейна) DP обычно строит таблицу dp[i][j] по двум измерениям: минимальная цена преобразования первых i символов строки a в первые j символов строки b.

Без memo рекурсивный fib делает много повторных вычислений.

Проверь себя: почему с memo сложность fib резко улучшается?

Когда выбирать жадный алгоритм

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

Примеры:

  • выбор интервалов по времени окончания в классической задаче scheduling;
  • некоторые виды размена монет;
  • простые задачи приоритизации по четкому критерию.

Дополнительные примеры "жадности" из задач:

  1. Сначала берём самые короткие задачи, пока не вышли за лимит времени.
const durationsSorted = [...durations].sort((a, b) => a - b);
let used = 0;
let done = 0;
for (const d of durationsSorted) {
  if (used + d > timeLimit) break;
  used += d;
  done += 1;
}
  1. Выбираем максимум непересекающихся интервалов, сортируя по времени окончания.
const sorted = [...meetings].sort((a, b) => a[1] - b[1]);
let count = 0;
let end = -Infinity;
for (const [start, finish] of sorted) {
  if (start >= end) {
    count += 1;
    end = finish;
  }
}

Когда выбирать DP

DP полезен, когда:

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

Примеры:

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

Реальные микро-сценарии

  1. Тарифный план.

DP может находить оптимальную комбинацию пакетов минут/гигабайт по цене.

  1. Планировщик задач.

Жадный подход выбирает ближайшую по дедлайну задачу для быстрых решений в UI-календаре.

  1. Складская комплектация.

DP помогает минимизировать издержки при множестве ограничений.

Частые ошибки новичков

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

Анти-провал: перед кодом всегда формулируй 3 вещи - состояние, переход, базовый случай.

Что будет, если изменить входные данные

В задаче размена монет жадный алгоритм может быть оптимальным для одних наборов номиналов и не оптимальным для других. Это edge case, который ломает "интуитивную" уверенность. DP в таких задачах чаще дает гарантированный оптимум, но может стоить дороже по ресурсам.

Проверь себя: если требования требуют строгий оптимум, какой подход безопаснее как базовый?

Краткий итог

  • Жадные алгоритмы быстрые и простые, но не всегда оптимальные.
  • Динамическое программирование запоминает подзадачи и чаще дает точный оптимум.
  • Выбор подхода зависит от свойств задачи, а не от личных предпочтений.
  • Для DP важно четко определить состояние, переход и базу.
  • В прод-коде ценится баланс: достаточная точность при адекватных затратах времени и памяти.