Урок

Двумерная динамика

Интуиция: когда одного индекса мало

В одномерной динамике состояние описывалось одним числом: «лучший ответ для первых i элементов». Бывают задачи, где одного числа не хватает, и ответ зависит сразу от двух величин:

Сетка. Чтобы описать, где ты стоишь, нужны строка i и столбец j.
Две строки. Нужно знать, сколько символов взято из первой строки (i) и сколько из второй (j).

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

Признак двумерной ДП: если ты говоришь «ответ для первых i символов одной строки и первых j символов другой» или «ответ для клетки (i, j)», состояние двумерное.

Пример 1: пути в сетке

Возьмём свою задачу (её нет в практике главы). Робот стоит в левом верхнем углу сетки n × m. За один шаг он может пойти вправо, вниз или по диагонали вправо-вниз. Сколькими способами он доберётся до правого нижнего угла?

Состояние: dp[i][j] — число способов дойти до клетки (i, j).

Переход: в клетку (i, j) можно прийти только из трёх соседних:

dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]

База: в первую строку можно попасть только движением вправо, поэтому там везде 1. В первый столбец можно попасть только движением вниз, там тоже везде 1.

Так выглядит таблица для сетки 3 × 4:

i \ j	0	1	2	3
0	1	1	1	1
1	1	3	5	7
2	1	5	13	25

Проверим одну ячейку: dp[2][2] = 5 (сверху) + 5 (слева) + 3 (диагональ) = 13. Ответ лежит в правом нижнем углу и равен 25.

Строку i = 2 мы заполняем слева направо. Когда указатель стоит на j = 3, все три нужных соседа уже посчитаны:

132

j ↓ 253

Строка i=2: dp[2][3] = 7 (сверху) + 13 (слева) + 5 (диагональ) = 25

Шаблон кода

def count_paths(n, m):
    # dp[i][j] — сколько способов дойти до клетки (i, j)
    dp = [[1] * m for _ in range(n)]  # первая строка и столбец = 1
    for i in range(1, n):
        for j in range(1, m):
            dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]
    return dp[n-1][m-1]

Пример 2: общая подпоследовательность двух строк

Здесь тоже две «оси», но это уже не координаты клетки, а длины префиксов. Подпоследовательность — это символы строки в исходном порядке, но не обязательно подряд. Состояние: dp[i][j] — длина наибольшей общей подпоследовательности первых i символов строки a и первых j символов строки b.

Главный приём: добавь строку и столбец для пустого префикса. Размер таблицы будет (len(a)+1) × (len(b)+1), а нулевые строка и столбец заполнятся нулями, потому что у пустой строки нет общих символов ни с какой другой. Так база задаётся сама собой, и не нужно отдельно разбирать случаи i = 0 или j = 0.

Таблица для a = "abc" и b = "ac":

	a	c
""	0	0
a	1	1
b	1	1
c	1	2

Ответ 2: общая подпоследовательность "ac". Каждая ячейка опять смотрит на соседей сверху, слева и по диагонали. Если символы a[i-1] и b[j-1] совпали, это сигнал воспользоваться диагональю. Точную формулу ты выведешь сам в практике, теперь ты знаешь, где её искать.

Порядок заполнения

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

Ячейка зависит от	Порядок обхода
верх, лево, диагональ ↖	строки сверху вниз, внутри слева направо
низ, право, диагональ ↘	строки снизу вверх, внутри справа налево

Если ячейка зависит только от предыдущей строки и от соседа слева в текущей, хранить всю таблицу не нужно. Достаточно одной-двух строк, и память падает с O(n·m) до O(m).

Сложность

Время: O(n · m). Каждую ячейку считаем один раз за O(1).
Память: O(n · m) для всей таблицы, O(m) с оптимизацией по строкам.

Как это звучит на собесе

«Состояние — dp[i][j]: ответ для префиксов длины i и j. Переход берёт значения сверху, слева и по диагонали. База — пустой префикс, нулевая строка и столбец. Заполняю построчно слева направо, ответ в dp[n][m]. Время O(nm), память можно сжать до одной строки».

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

Частые ошибки

Путаница с индексами. При таблице размера n+1 символ для dp[i][j] — это a[i-1], а не a[i].
Забытая база. Нулевая строка и столбец заполнены неправильно, и ошибка расползается по всей таблице.
Неверный порядок обхода. Ячейка читает соседа, который ещё не посчитан.
Перепутаны n и m. Особенно легко это сделать при создании массива: [n][m] против [m][n].
Переполнение. Число путей растёт очень быстро, поэтому бери long.
Сжатие до одной строки без проверки. Значение диагонали dp[i-1][j-1] перезаписывается раньше, чем ты его прочитал. Сохрани его во временную переменную.

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