Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

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

Динамическое программирование — это когда у нас есть задача, которую непонятно как решать, и мы разбиваем ее на меньшие задачи, которые тоже непонятно как решать. (с) А. Кумок.

Скажем что-то более оптимистичное. Динамическое программирование или метод динамической оптимизации — это подход к решению задач путем разбиения их на более мелкие задачи, дальнейшим решением мелких задач и запоминанием ответа.

Пример: найти n-ое число Фибоначчи. Первые два числа 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел. 0, 1, 1, 2, 3, 5, 8, 13, …

Рекурсивное решение задачи

const getFibonacci = (n) => {
  if (n < 0) {
    return null;
  }
  if (n < 2) {
    return n;
  }

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

Чтобы вычислить n-oe число, нужно узнать n-oe-2 и n-oe-1. Некоторые значения будут пересчитываться по второму разу, поэтому такая функция вряд ли найдет нам даже 50-ое число. Или мы будем ждать очень долго.

Основное правило динамического программирования - свести задачу для n к задаче для чисел, меньших, чем n. То есть, если нужно найти 10-ое число Фибоначчи, найдем 1-ое число. Здесь нам повезло, мы знаем, что это 0. Для первого смогли, сможем и для второго, это будет 1. Смогли для второго, сможем и для 3-его - будет 1. И так далее, по индукции.

const getFibonacci = (n) => {
  let first = 0;
  let second = 1;

  if (n < 0) {
    return null;
  }
  if (n < 2) {
    return n;
  }

  let result = 0;
  for (let index = 3; index <= n + 1; index++) {
    result = first + second;
    first = second;
    second = result;
  }

  return result;
};

Чтобы решать задачи динамикой, нужно знать:

  • Cостояние динамики - параметры. Для чисел Фибоначчи это номер числа в последовательности.
  • Значения начальных состояний. Состояния, которые уже нам известны или состояния, которые можно подсчитать не прибегая к предыдущим.
  • Переходы между состояниями, формула пересчета. Сейчас мы использовали готовую формулу, getFibonacci(n - 2) + getFibonacci(n - 1), но зачастую приходится самостоятельно выводить формулы, понимать из текстового описания задачи, как перейти к следующему состоянию.
  • Порядок пересчета. В примере выше мы считали динамикой назад, смотрели на предыдущие значения и вычисляли текущее. Динамика вперед - то же самое, только мы будем на основе текущего значения, вычислять будущее значение. Так же мы можем вычислять рекурсивно, но динамически оптимизировать. Проблема рекурсии была в том, что мы постоянно пересчитывали значения, которые считали ранее, но их можно просто сохранить! Такое обычно называют мемоизацией.
const fibonacciSequence = [0, 1];
const getFibonacci = (n) => {
  if (n < 0) {
    return null;
  }
  if (fibonacciSequence[n]) {
    return fibonacciSequence[n];
  }

  fibonacciSequence[n] = getFibonacci(n - 2) + getFibonacci(n - 1);
  return fibonacciSequence[n];
};
  • Расположение ответа на задачу. Исходя из задачи бывает, что это сумма каких-то состояний, максимум, или что-то иное.

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


Аватары экспертов Хекслета

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты.

Ошибки, сложный материал, вопросы >
Нашли опечатку или неточность?

Выделите текст, нажмите ctrl + enter и отправьте его нам. В течение нескольких дней мы исправим ошибку или улучшим формулировку.

Что-то не получается или материал кажется сложным?

Загляните в раздел «Обсуждение»:

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

Об обучении на Хекслете

Для полного доступа к курсу нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
900
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.

  • 130 курсов, 2000+ часов теории
  • 900 практических заданий в браузере
  • 360 000 студентов
Даю согласие на обработку персональных данных, соглашаюсь с «Политикой конфиденциальности» и «Условиями оказания услуг»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff

Используйте Хекслет по максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Даю согласие на обработку персональных данных, соглашаюсь с «Политикой конфиденциальности» и «Условиями оказания услуг»