Динамика по сетке

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

Задача-образец: из левого верхнего угла поля надо попасть в правый нижний, двигаясь только вправо и вниз. Сколько путей?

Состояние: dp[r][c] — сколько путей ведёт в клетку $(r, c)$.

Переход: в клетку попадают сверху или слева, и эти пути не пересекаются — последний шаг у них разный. Значит dp[r][c] = dp[r-1][c] + dp[r][c-1].

База: dp[0][0] = 1. В первой строке и первом столбце дорога одна, но это следствие, а не отдельное правило: считать их лучше тем же переходом, просто отсутствующие соседи дают ноль.

dp = [[0] * m for _ in range(n)]
dp[0][0] = 1
for r in range(n):
    for c in range(m):
        if r > 0:
            dp[r][c] += dp[r - 1][c]
        if c > 0:
            dp[r][c] += dp[r][c - 1]

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

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

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

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

Препятствие в динамике — это состояние, в которое нельзя попасть. Оформляется оно естественно: у стены ноль путей.

if grid[r][c] == "#":
    dp[r][c] = 0
    continue

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

Где на этом ошибаются

Соблазнительно задать первую строку и первый столбец константой — «туда ведёт одна дорога». В поле без стен это верно. В поле со стенами — нет: за стеной путей ноль, и все клетки строки после неё недостижимы.

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

Минимум вместо количества

Всё то же самое, только вместо сложения — минимум. И одна тонкость: ноль и «недостижимо» надо различать. Нулевая плата законна, а если пометить нулём недостижимую клетку, она окажется самой выгодной и испортит ответ.

Помечайте недостижимость бесконечностью и проверяйте перед прибавлением:

best = min(from_left, from_top)
dp[r][c] = INF if best == INF else best + cost[r][c]

Поле состоит из одной строки: . # . — свободно, стена, свободно.

Сколько путей ведёт из левой клетки в правую?

Таблица $2000 \times 2000$ — четыре миллиона чисел. В Python список списков такого размера займёт больше сотни мегабайт, и это уже повод задуматься.

Присмотримся к переходу: dp[r][c] зависит от dp[r-1][c] и dp[r][c-1]. То есть от строки выше и от левого соседа в той же строке. Ничего больше не нужно.

Значит хватит одной строки:

row = [0] * m
row[0] = 1
for r in range(n):
    for c in range(m):
        if c > 0:
            row[c] += row[c - 1]

Тонкость, ради которой это работает: когда мы обрабатываем клетку $c$, в row[c] ещё лежит значение предыдущей строки — то самое dp[r-1][c], — а в row[c-1] уже новое, из текущей строки. Ровно два слагаемых, которые и нужны.

Направление обхода становится важным

Пока переход смотрит влево, строку обновляют слева направо. Но так бывает не всегда.

В задаче о рюкзаке состояние — «наибольшая ценность при вместимости $t$», а переход берёт dp[t - вес], где значение должно быть без текущего предмета. Если идти слева направо, dp[t - вес] успеет обновиться, и предмет попадёт в рюкзак дважды. Поэтому веса перебирают справа налево.

Это общее правило сжатия: сначала выясните, какие значения переход обязан читать «старыми», и выберите направление так, чтобы они не успели обновиться.

Когда сжимать нельзя

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

Поле $3 \times 3$ без стен, ходить можно вправо и вниз.

Сколько путей ведёт из левого верхнего угла в правый нижний? Введите целое число.

Двумерная таблица возникает не только там, где в условии нарисована сетка. Гораздо чаще сетка появляется сама — как пара номеров в двух последовательностях.

Общая подпоследовательность

Даны две строки, надо найти длину наибольшей общей подпоследовательности.

Состояние: dp[i][j] — ответ для первых $i$ символов первой строки и первых $j$ второй. Никакого поля в условии нет, а таблица — есть.

if first[i - 1] == second[j - 1]:
    dp[i][j] = dp[i - 1][j - 1] + 1        # символы совпали, берём оба
else:
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])   # от одного отказываемся

Подстрока вместо подпоследовательности

Разница в одну строчку. Подстрока состоит из подряд идущих символов, поэтому при несовпадении цепочка обрывается:

dp[i][j] = 0        # вместо наследования максимума

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

Расстояние редактирования

Три операции дают три перехода: удаление смотрит вверх, вставка — влево, замена — по диагонали. База — превращение в пустую строку: $i$ удалений или $j$ вставок.

Замечайте это сходство: как только в задаче два независимых «указателя», которые двигаются вперёд, — почти наверняка перед вами двумерная таблица.

База задана константой, а не посчитана. Разобрано выше. Первая строка со стеной ловит это мгновенно.

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

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

Ноль вместо «недостижимо». В задачах на минимум недостижимая клетка с нулём становится самой выгодной.

Таблица не помещается в память. Считайте $n \cdot m$ заранее. Четыре миллиона чисел в списке списков — это уже сотня мегабайт.

Ответ взят из угла, хотя он в максимуме. У подстроки и у квадрата ответ — максимум по таблице, а не последняя клетка.

Как проверять себя

• поле $1 \times 1$ и поле из одной строки;
• стена в первой строке или первом столбце — ловит базу-константу;
• поле без стен — ответ должен совпасть с числом сочетаний из занятия по комбинаторике;
• все числа нулевые — ловит путаницу нуля с недостижимостью.

Лестница прежняя: пять разминочных, семь основных, три со звёздочкой. Зачёт при десяти решённых.

Начинайте с тех же трёх вопросов, а четвёртым добавляйте порядок обхода: что должно быть посчитано раньше.

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

Задача: «дано поле из свободных клеток и стен; сколько путей ведёт из левого верхнего угла в правый нижний ходами вправо и вниз? Углы свободны».

Ученик написал:

n, m = map(int, input().split())
grid = [input() for _ in range(n)]

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

for c in range(m):
    dp[0][c] = 1
for r in range(n):
    dp[r][0] = 1

for r in range(1, n):
    for c in range(1, m):
        if grid[r][c] == "#":
            dp[r][c] = 0
        else:
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1]

print(dp[n - 1][m - 1])

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

Постройте вход, на котором видно расхождение, объясните причину и предложите исправление.