Не бойтесь динамического программирования / Хабр

Говорят, все боятся задач на динамическое программирование (aka ДП), потому что их решения выглядят как из задачника по матанализу. А мне оно всегда нравилось. Одна изящная формула вроде

— и задача решена.

В этой статье разберем три задачи по динамическому программированию с LeetCode и попробуем каждый раз прийти к изящной формуле интуитивно. Также обсудим, по каким признакам можно понять, что задача — на динамическое программирование.

Задача 62. Unique Paths (Medium)

Робот двигается по доске размером m x n из верхнего левого угла (0, 0) в правый нижний (m − 1, n − 1). Допускаются шаги либо вниз, либо вправо. Найти количество всех возможных уникальных маршрутов, по которым он может достичь цели.

С точки зрения математика ответ можно дать за полминуты. Обратите внимание, что любой путь — это просто последовательность шагов вниз (обозначим их D) и вправо (R). Количество этих шагов соответствует размерам доски: вниз придется сделать m-1 шагов, а вправо – n-1 шагов, а в сумме – m+n-2 шага. А вот последовательность этих шагов может меняться:

DDRRR
DRDRR
RRDDD
…

Фактически выбрать путь – значит выбрать, в какие из m+n-2 позиций поставить символы D, заняв остальные символами R (или наоборот). Сколькими способами можно выбрать m - 1 позиций для символа D из m + n - 2 доступных? Как известно из комбинаторики, выбор k элементов из n без учета порядка вычисляется по формуле

$C_n^k = \binom{n}{k} = \frac{n!}{k!(n-k)!}$

В нашем случае количество путей равно

$C_{m+n-2}^{m-1} = \binom{m+n-2}{m-1}$

Но у нас собеседование не по математике, а по алгоритмам, поэтому давайте писать алгоритм.

Если доска состоит из одной строки, то есть m=1, то в ней возможен всего один путь. То же самое верно для n=1.

Перейдем к более общей задаче. Сколькими способами можно попасть в клетку (i, j)? По условию, в нее можно прийти либо сверху из (i-1, j), либо слева из (i, j-1). И эти пути гарантированно различаются как минимум последним шагом (сверху/слева).

Если пути гарантированно различаются, то применимо правило сложения: если множество A содержит n вариантов, множество B содержит m вариантов и A ∩ B = ∅, то общее число вариантов равно n + m. Для нашего случая из него следует, что число путей, которыми можно прийти в точку (i, j), равно сумме числа путей, которыми можно прийти в точку (i-1, j), и числа путей, которыми можно прийти в точку (i, j-1).

Чтобы воспользоваться этим соотношением на практике, придется хранить количество путей для уже рассмотренных клеток. Введем матрицу dp размером m x n, в которой элемент dp[i][j] обозначает количество различных путей из стартовой клетки (0, 0) в клетку (i, j) на доске.

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

Как вычислить значение dp[i][j], мы уже вывели:

Теперь матрица dp может быть заполнена последовательно — строка за строкой или столбец за столбцом — так как для вычисления каждой ячейки используются только уже известные значения.

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

Формула готова, а написать по ней код очень просто:

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]

        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        
        return dp[m - 1][n - 1]

Runtime 0ms
Beats 100.00%

Алгоритм проходит по всем клеткам доски ровно один раз, поэтому его временная сложность равна O(m · n).

Динамическое программирование — один из самых изящных способов решать олимпиадные задачи. Но его можно применять только при двух условиях:

1. Оптимальная подструктура. Оптимальное решение задачи содержит в себе оптимальные решения подзадач. Например, в данном случае число путей в клетку (i, j) определялось из суммы числа путей в две соседние клетки (i-1, j) и (i, j-1).

2. Перекрывающиеся подзадачи. Одни и те же подзадачи возникают многократно. В данной задаче одна и та же клетка (i, j) может быть достигнута множеством различных способов. При переборе всех путей количество путей до этой клетки пришлось бы вычислять снова и снова.

Задача 64. Minimum Path Sum (Medium)

Нам дана прямоугольная таблица m × n, заполненная неотрицательными числами.
Мы стартуем в левом верхнем углу (0, 0) и за один шаг можем двигаться только вправо или вниз. Необходимо дойти до правого нижнего угла (m − 1, n − 1) так, чтобы сумма всех чисел на пути (назовем ее стоимостью) была минимальной.

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

Например, в этом массиве первым оптимальным шагом кажется движение вправо, потому что в клетке (0, 1) стоит число меньше, чем в клетке (1, 0). Но на следующем шаге мы попадем в ловушку, потому что и вправо, и вниз стоят клетки с числом 1000.

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

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

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

Пусть dp[i][j] — минимальная стоимость пути до клетки (i, j), включая текущую клетку.

По условию задачи все пути начинаются в левом верхнем углу (0, 0). Стоимость пути в эту клетку равна значению этой клетки:

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

По той же причине в каждую клетку первого столбца можно прийти только сверху, и для j=0 выполняется

Теперь посмотрим на остальные клетки. Попасть в клетку (i, j) можно либо из клетки сверху (i − 1, j), либо из клетки слева (i, j − 1). К этому моменту минимальные стоимости путей в обе эти клетки уже вычислены. Значит, остается выбрать более дешевый из этих двух маршрутов и добавить значение текущей клетки:

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

После заполнения всей таблицы значение в правом нижнем углу dp[m − 1][n − 1] и будет минимальной возможной стоимостью пути от стартовой клетки (0, 0) до финиша.

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        dp = [[0] * n for _ in range(m)]

        dp[0][0] = grid[0][0]

        for j in range(1, n):
            dp[0][j] = grid[0][j] + dp[0][j - 1]

        for i in range(1, m):
            dp[i][0] = grid[i][0] + dp[i - 1][0]

        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = grid[i][j] + min(
                    dp[i - 1][j],
                    dp[i][j - 1]
                )

        return dp[-1][-1]

Сложность решения по времени снова равна O(m · n), так как мы прошли по всем m строкам и n столбцам ровно один раз.

Задача 70. Climbing Stairs (Easy)

Вот видите, задачка на динамическое программирование, а уровень —Easy. Даже сам LeetCode не считает ДП чем-то сложным.

Человек поднимается по лестнице с n ступенями (1 <= n <= 45). На каждом шаге он преодолевает либо 1, либо 2 ступени. Сколько различных способов у него есть, чтобы добраться до вершины?

Начнем с n=1. Подняться на 1 ступеньку можно только одним способом, преодолев ровно 1 ступеньку.

Для n=2 существует два способа: сделать два шага по 1 ступеньке (1+1) или одним махом подняться на 2.

На 3-ю ступеньку можно подняться тремя способами: 1+1+1, 1+2, 2+1.

На 4-ю – даже пятью:

1 + 1 + 1 + 1

1 + 2 + 1

2 + 1 + 1

1 + 1 + 2

2 + 2

Давайте сгруппируем слагаемые:

(1 + 1 + 1) + 1

(1 + 2) + 1

(2 + 1) + 1

(1 + 1) + 2

(2) + 2

Ничего не напоминает?

На n-ю ступеньку можно подняться либо с n-1, либо с n-2. Соответственно, число способов, которыми можно подняться на n-ю ступеньку, равно сумме способов, которыми можно подняться на две предыдущие. Фактически мы пришли к числам Фибоначчи: каждое следующее число равно сумме двух предыдущих. Только мы начинаем не с 0, а с 1.

Если мы реализуем классическую рекурсию для вычисления чисел Фибоначчи:

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)

— то уже при n=44 упремся в Time Limit Exceeded. Хотя рекурсия глубиной 44 уровня легко помещается в стек вызовов, алгоритм повторно вычисляет одни и те же значения:

climbStairs(44)
    ├─ climbStairs(43)
    │   ├─ climbStairs(42)
    │   │   ├─ climbStairs(41)
    │   │   │   ├─ climbStairs(40)
    │   │   │   └─ climbStairs(39)
    │   │   └─ climbStairs(40)
    │   └─ climbStairs(41)
    │       ├─ climbStairs(40)
    │       └─ climbStairs(39)
    └─ climbStairs(42)
        ├─ climbStairs(41)
        │   ├─ climbStairs(40)
        │   └─ climbStairs(39)
        └─ climbStairs(40)

Это приводит к катастрофическому росту числа операций. Точнее, экспоненциальному: количество вызовов растет как O(φⁿ), где φ ≈ 1.618 — золотое сечение). Для n=44 получается более миллиарда вызовов функции, что превышает типичный лимит времени на платформах типа LeetCode (1-2 секунды).

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

@lru_cache(None)

перед сигнатурой метода climbStairs().

Но interview-friendly решение не ищет легких путей, поэтому давайте сохраним промежуточные решения вручную.

Обратите внимание, что эта задача обладает всеми признаками задач на динамическое программирование:

1. Оптимальная подструктура. Количество способов подняться на n-ю ступеньку полностью определяется решениями для меньших задач: для (n − 1)-й ступеньки и для (n − 2)-й.

2. Перекрывающиеся подзадачи. Одни и те же подзадачи вычисляются многократно в разных ветках рекурсии.

Наличие обоих признаков означает, что задачу можно решать методом динамического программирования, сохраняя результаты подзадач для повторного использования. Промежуточные решения будем хранить в массиве dp, где dp[i] — количество способов подняться на i-ю ступеньку.

Как уже говорилось, на первую ступеньку можно подняться одним способом, а на вторую – двумя:

В общем случае число способов, которыми можно подняться на i-ю ступеньку, равно сумме способов, которыми можно подняться на две предыдущие:

Заполнив этот массив на длину n, мы получим ответ:

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n

        dp = [0] * (n + 1)

        dp[1] = 1
        dp[2] = 2

        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]

        return dp[n]

В отличие от предыдущих задач, этот алгоритм имеет линейную временную сложность O(n), так как каждая подзадача решается единственный раз и повторных вычислений не происходит.

Runtime 0ms
Beats 100.00%

Вывод

Как видите, задачи на динамическое программирование не так уж сложны. Главное при их решении:

определить, есть ли признаки ДП — оптимальная подструктура и перекрывающиеся подзадачи
и вывести формулу.

А написание кода по готовой формуле так просто, что с ним справится даже тот, кто только вчера начал учить Python.

Кстати, если вы хотите увидеть решения этих задач на других языках программирования или если вас интересуют решения других типичных задач LeetCode — добро пожаловать на мой курс «Алгоритмы для собеседований на Python/Kotlin/C++/C#/PHP».