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

Что такое динамическое программирование?

Это метод оптимизации, который решает сложные задачи, разбивая их на более простые подзадачи.
Основная идея: если мы можем решить большую проблему, используя решения меньших подпроблем, и эти подпроблемы повторяются, мы можем сохранить их решения, чтобы не вычислять их снова.

Ключевые концепции

a. Оптимальная подструктура:

Оптимальное решение большой проблемы состоит из оптимальных решений её подпроблем.
Пример: кратчайший путь от A до C через B - это комбинация кратчайших путей A→B и B→C.

b. Перекрывающиеся подпроблемы:

Одни и те же подпроблемы встречаются многократно. Вместо повторного решения, мы сохраняем результаты в структуре данных (обычно массив или хеш-таблица).

Подходы к ДП

a. Сверху вниз (Мемоизация):

Начинаем с основной проблемы и рекурсивно разбиваем её на подпроблемы.
Используем кэш (обычно массив или Map) для хранения результатов.
Перед вычислением проверяем, нет ли результата в кэше.

b. Снизу вверх (Табличный):

Начинаем с самых маленьких подпроблем.
Итеративно строим решения больших проблем из меньших.
Заполняем таблицу (массив) в определенном порядке.

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

Пример кода без ДП

var fibonacci = function (n) {
  if (n == 0) {
    return 0;
  }

  if (n == 1) {
    return 1;
  }

  return fibonacci(n - 1) + fibonacci(n - 2);
};

Пример кода с ДП - мемоизация

var fibonacci = function (n) {
  if (n == 0) {
    return 0;
  }

  if (n == 1) {
    return 1;
  }

  if (memo.has(n)) {
    return memo.get(n);
  }

  memo.set(n, fibonacci(n - 1) + fibonacci(n - 2));
  return memo.get(n);
};

let memo = new Map();

Шаги для решения задач ДП

a. Определить подпроблемы и их структуру.
b. Написать рекуррентное соотношение между подпроблемами.
c. Определить базовые случаи.
d. Выбрать подход (сверху вниз или снизу вверх).
e. Реализовать решение.

Преимущества

• Эффективно решает задачи с повторяющимися вычислениями.
• Часто превращает экспоненциальную сложность в полиномиальную.

Недостатки

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

Когда применять

Задачи, которые следует решать с помощью динамического программирования (ДП), обычно имеют две основные характеристики:

В задаче требуется найти оптимальное значение (максимум или минимум) чего-либо или количество способов сделать что-либо.

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

На каждом шаге вам нужно принимать "решение", и эти решения влияют на будущие решения.

Решение может заключаться в выборе между двумя элементами.
Влияние решений на будущие решения может быть чем-то вроде: "если вы берете элемент x, то вы не можете взять элемент y в будущем".

Примечание к первой характеристике: не все задачи, сформулированные в этих форматах, предназначены для решения с помощью ДП, и не все задачи ДП сформулированы в одном из этих форматов. Однако в качестве общего руководства эти характеристики очень хорошо себя зарекомендовали.

Оптимальное значение или количество:

ДП часто используется, когда нужно найти "лучший" вариант.
"Лучший" может означать минимальный (стоимость, расстояние) или максимальный (прибыль, длина).
Также ДП отлично подходит для подсчета количества способов достижения цели.

Принятие решений:

Ключевая идея: текущий выбор влияет на будущие возможности.
Простой пример: выбор между двумя предметами.
Сложный пример: выбор предмета A исключает выбор предмета B позже.
Эта зависимость создает "состояния", которые идеально подходят для ДП.

Форматы задач:

"Какова минимальная стоимость..." - например, наименьшая стоимость достижения цели в графе.
"Какова максимальная прибыль..." - например, максимальная прибыль от торговли акциями.
"Сколько способов..." - например, сколько способов достичь вершины лестницы.
"Самая длинная..." - например, самая длинная возрастающая подпоследовательность.

Важное предупреждение:

Не все задачи, звучащие так, решаются с помощью ДП.
"Найти максимум в массиве" не требует ДП.
"Найти кратчайший путь в невзвешенном графе" - это BFS (Breadth-First Search = Поиск в ширину), не ДП.

И наоборот:

Некоторые задачи ДП не имеют такого явного формата.
Например, "рассчитать стоимость покраски домов" - это ДП, хотя формулировка не стандартная.

Руководство, а не правило:

Эти характеристики - хорошие индикаторы, но не строгие критерии. Они помогают "почувствовать", подходит ли ДП для задачи. С опытом вы научитесь распознавать другие признаки задач ДП.

Суть в том, что динамическое программирование часто применяется в задачах, где:

• Нужно найти что-то оптимальное или посчитать количество вариантов.
• Текущие решения влияют на будущие возможности.

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