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

Мы уже рассказывали про идею и метод динамического программирования: это одна из парадигм мышления в теории алгоритмов, которая раскладывает крупные задачи на более простые составляющие.

Сегодня разберём этот принцип на других примерах и посмотрим, как динамическое программирование выглядит в коде.

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

Кратко вспомним, о чём речь.

Динамическое программирование — это разбиение сложной крупной задачи с большим количеством вариантов решений на подзадачи. Например, нужно прийти из точки А в точку Б и между ними есть ещё большое количество промежуточных пунктов. Поиск пути между отдельными пунктами — это небольшие подзадачи, к каждой из которых можно быстро найти короткое оптимальное решение.

Теперь, если сложить эти короткие результаты, получится одно оптимальное решение для маршрута между А и Б.

Ключевые принципы метода

Основная магия в том, что называется «принципом оптимальности Беллмана»: если всё решение оптимальное, то и каждая его часть тоже будет оптимальной. Именно поэтому мы можем быстро найти промежуточные результаты и сложить в одно целое.

В динамическом программировании очень важно, что мы не храним полные решения для каждого промежуточного фрагмента. Для финального решения достаточно ответов: это ускоряет работу всего процесса и экономит усилия и ресурсы.

Вам может быть интересно:

Динамическое программирование: простой способ приручить сложные задачи

Динамическое программирование для установления последовательности работ

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

Когда команде нужно закончить большой проект, он редко состоит из одного типа задач: дизайна, фронтенда или UI. Скорее всего, они будут пересекаться и дополнять друг друга. Динамическое программирование может помочь составить правильный план, когда и что следует делать. Это и есть установление последовательности работ.

Например, для финального продукта нужно:

Часть из этих направлений можно делать параллельно — например, дизайн и бэкенд. Но какие-то работы зависят друг от друга: без готового кода нельзя тестировать, а без тестирования — раскладывать на сервере.

Пример использования в управлении проектами и построении сетевых графиков

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

Это упрощённый пример, на котором каждая новая стадия зависит от всех предыдущих: пока не будут выполнены 2, 3 и 4-й этапы, нельзя начать 5, 6 и 7-й. Но иногда зависимость может быть и не такая прямая: 7-й этап зависит от 2-го, а 5-й — от 3-го.

Как метод помогает найти критический путь и минимизировать время

Критический путь — это цепочка зависимостей, которая определяет минимально возможный срок всего проекта, то есть оптимальное решение.

Главная идея:

Задачи, которые нельзя задерживать, образуют критический путь.

В итоге получается, что мы считаем самое лучшее время для всего проекта — это наша большая задача. Но считаем мы это время через получение сроков для каждого промежуточного этапа — это наши промежуточные задачи. Поэтому такая декомпозиция проекта — один из частых примеров, где может использоваться динамическое программирование.

Нисходящее и восходящее динамическое программирование

Есть два варианта реализации динамического программирования. Общая идея одна, но пути реализации разные.

Нисходящее динамическое программирование называют ещё Top-Down или «мемоизация».

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

Восходящее динамическое программирование называют Bottom-Up или «табуляция».

Ещё такой подход называют заполнением таблицы, потому что его смысл в том, что мы начинаем с самых простых задач и идём вверх. Мы решаем всё по порядку, сохраняя результаты и как бы занося их в таблицу.

Дальше мы разберём оба подхода с простыми примерами на Python.

Плюсы и минусы каждого метода

Нисходящее программирование Top-Down хорошо тем, что это простой и естественный код, который считает только нужные подзадачи. Он включает рекурсию, которая скрывает детали, поэтому для считывания это удобнее.

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

Плюс восходящего программирования в том, что оно быстрое и почти всегда эффективнее нисходящего. В нём нет рекурсии и опасности ошибки из-за перегрузки. Ещё при этом подходе легче оптимизировать память, потому что при мемоизации можно хранить только некоторые значения. Так нужно делать не всегда, но иногда полезно.

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

Пример — вычисление чисел Фибоначчи на Python

Число Фибоначчи — число последовательности, где первые два числа равны 0 и 1, а все остальные получаются через сложение двух предыдущих чисел. Получается, для получения любого числа нам нужно рассчитать два предыдущих.

Мы не можем сказать наверняка, что любое произвольное число будет подходить под условие Фибоначчи, поэтому наша программа будет вычислять число по номеру последовательности: мы отправляем в программу номер n, а система возвращает число.

Сначала — нисходящий подход. 

Код выглядит так:

# функция вычисляет n-е число Фибоначчи с запоминанием подзадач
def fib(n, memo={}):
    # базовый случай: fib(0) = 0 и fib(1) = 1
    if n <= 1:
        return n

    # если результат уже есть в словаре, возвращаем его
    if n in memo:
        return memo[n]

    # иначе вычисляем fib(n-1) и fib(n-2), сохранить сумму в memo
    memo[n] = fib(n-1, memo) + fib(n-2, memo)

    # возвращаем сохранённый результат
    return memo[n]

# выводим пример вычисления
print(fib(10))

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

У нас есть два начальных числа Фибоначчи: это 0 и 1. Если номер числа равен 0 и 1, программа сразу возвращает это же число.

Тут есть интересное расхождение между реальными человеческими числами Фибоначчи и компьютерными. Если по-настоящему, то 1-й элемент последовательности — это 0. Но если мы запросим его у программы, то получим 1. Так происходит из-за того, что код считает элементы по индексам, начиная с 0. 

Можно скорректировать работу программы и сделать так, чтобы она отвечала человеческим представлениям о нумерации. Но тогда архитектура системы не будет соответствовать общепринятым принципам программистов. Поэтому при работе с кодом всегда нужно учитывать, что могут возникнуть нюансы, — просто потому, что компьютеры работают и считают немного по-своему.

Проверив два базовых случая, идём дальше. Если пользователь запросил другой номер, программа проверяет, не сохранён ли результат вычисления этого номера в словаре memo. Если сохранён — сразу возвращаем его.

Если запрошенного номера в memo нет, функция fib() рекурсивно запускает саму себя до тех пор, пока не дойдёт до базового случая, когда нужно посчитать fib(0). После этого программа считает и сохраняет в словарь все предыдущие числа последовательности и вычисляет нужное для ответа пользователю.  

У нас в примере пользователь запрашивает 10-е число, и при запуске получаем:

55

Теперь восходящее. Выглядит так:

# функция вычисляет n-е число Фибоначчи, заполняя таблицу снизу вверх
def fib(n):
    # базовый случай для n = 0 и n = 1
    if n <= 1:
        return n

    # создаём список для хранения значений
    dp = [0] * (n + 1)

    # записываем первые два значения вручную
    dp[0] = 0
    dp[1] = 1

    # заполняем таблицу от 2 до n
    for i in range(2, n + 1):
        # текущее значение = сумма двух предыдущих
        dp[i] = dp[i-1] + dp[i-2]

    # возвращаем результат fib(n)
    return dp[n]

# выводим пример вычисления
print(fib(10))

Базовые случаи работают похожим образом: если пользователь запрашивает 0 или 1, сразу возвращаем это же значение. 

Если нужно что-то больше 0 и 1 — идём дальше и создаём список dp. Первые два значения записываем вручную. Записываем только два, потому что в базовой ситуации проверяем только их. После этого идём снизу вверх — заполняем список числами Фибоначчи, вычисляя каждое как сумму двух предыдущих. Первые два у нас уже есть, потому что их мы вставили вручную. В конце возвращаем результат.

Обратите внимание, что во всей функции нет применения рекурсии, то есть вызовов себя.

При запуске получаем то же самое, что при нисходящем программировании:

55

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

Задача о наборе лестницы или о кузнечике

В чём задача: есть человек внизу лестницы или кузнечик перед полосой из клеток. Человек передвигается по лестнице вверх, кузнечик — по клеткам вперёд. Перемещаться можно на 1 или 2 ступени или клетки. Вопрос в том, сколькими способами можно дойти до определённой ступени или клетки?

Эта программа будет немного сложнее, поэтому мы пойдём по частям.

Создаём функцию и проверяем количество ступеней (клеток). Если это число отрицательное, способов переместиться нет:

# функция считает количество способов добраться до ступеньки n, шагая на 1 или 2
def count_ways_stairs(n):
   # если n отрицательное, способов нет
   if n < 0:
       # возвращаем 0 способов
       return 0

Если число равно 0, есть только один способ: не делать ничего и стоять на месте. На 1-ю ступень тоже можно попасть только одним путём: шагнуть на 1 ступень. Записываем это в программу отдельно:

    # если нужно стоять на месте (n=0), есть только один способ: ничего не делать
    if n == 0:
        # возвращаем 1 способ
        return 1

    # если n=1, есть только один способ: шаг на 1
    if n == 1:
        # возвращаем 1 способ
        return 1

Заводим переменные для каждого из этих базовых случаев:

    # заводим переменную для способов попасть на i-2 (начнём с dp[0]=1)
    prev2 = 1

    # заводим переменную для способов попасть на i-1 (dp[1]=1)
    prev1 = 1

Теперь главное. Чтобы попасть на нужную последнюю ступень, мы можем перешагнуть с неё либо с позиции «1 ступень назад», либо «2 ступени назад». 

Вначале нужно посчитать, сколькими способами мы можем попасть на позицию 2. Для этого складываем количество способов для 2 предыдущих позиций. Это то, что мы занесли в программу для позиций 0 и 1, — по одному способу для каждой позиции. Получается, что на ступень 2 можно попасть двумя разными способами. Это правда: можно перешагнуть на две ступени, а можно два раза на одну.

Количество позиций для нужной ступени будем хранить в переменной cur. Для подсчёта будем использовать цикл: проходить по числам от 2 до финальной ступени и складывать количество способов для двух предыдущих ступеней. 

Это звучит непонятно, но в коде выглядит проще — тут просто сложение в первом действии и два раза обновление предыдущих значений.

# перебираем ступеньки от 2 до n включительно
for _ in range(2, n + 1):
   # текущие способы = способы на (i-1) + способы на (i-2)
   cur = prev1 + prev2
   # сдвигаем prev2 вперёд: prev2 становится старым prev1
   prev2 = prev1
   # сдвигаем prev1 вперёд: prev1 становится текущим значением
   prev1 = cur

# возвращаем количество способов для ступеньки n
return prev1

После получения нужного числа обновляем предыдущие ступени, сдвигая их на 1 вперёд. В конце обновляем значение переменной prev1 и возвращаем именно его, потому что cur — временная переменная, которая используется только внутри цикла.

После этого можно запускать функцию и передавать в неё количество ступеней или клеток. Например:

print(count_ways_stairs(5))

Получаем ответ:

8

# функция считает количество способов добраться до ступеньки n, шагая на 1 или 2
def count_ways_stairs(n):
   # если n отрицательное, способов нет
   if n < 0:
       # возвращаем 0 способов
       return 0

   # если нужно стоять на месте (n=0), есть только один способ: ничего не делать
   if n == 0:
       # возвращаем 1 способ: dp[0]=1
       return 1

   # если n=1, есть только один способ: шаг на 1
   if n == 1:
       # возвращаем 1 способ: dp[1]=1
       return 1

   # заводим переменную для способов попасть на i-2 (начнём с dp[0]=1)
   prev2 = 1

   # заводим переменную для способов попасть на i-1 (начнём dp[1]=1)
   prev1 = 1

   # перебираем ступеньки от 2 до n включительно
   for _ in range(2, n + 1):
       # текущие способы = способы на (i-1) + способы на (i-2)
       cur = prev1 + prev2
       # сдвигаем prev2 вперёд: теперь prev2 станет старым prev1
       prev2 = prev1
       # сдвигаем prev1 вперёд: теперь prev1 станет текущим значением
       prev1 = cur

   # возвращаем количество способов для ступеньки n
   return prev1


# пример использования: печатаем ответ для n=5
print(count_ways_stairs(5))

Что дальше

Мы немного разобрали динамическое программирование, но ещё осталось много интересного. Есть много других алгоритмических парадигм и разделов, и даже в самом динамическом программировании можно попробовать делать другие вещи. Например, написать программу сравнения биологических цепочек, которая сложнее и нагляднее показывает плюсы и ограничения парадигмы. Это в следующий раз.

Любишь Python? Зарабатывай на нём!

Изучите самый модный язык программирования и станьте крутым бэкенд-разработчиком. Старт — бесплатно.

Попробовать бесплатно