Динамика по таблице

Второй по частоте вид динамики: состояние — пара индексов, таблица двумерная.

Пути в сетке

Из левого верхнего угла доски $n \times m$ надо попасть в правый нижний, разрешены ходы вправо и вниз. Сколько маршрутов?

Перебором — безнадёжно: на доске $15 \times 15$ маршрутов 40 116 600, на $20 \times 20$ — уже 35 345 263 800.

Динамикой — четыре строки. Состояние: $d[i][j]$ — число маршрутов до клетки $(i, j)$. Переход: пришли сверху или слева. База: $d[0][0] = 1$. Порядок: по строкам сверху вниз, внутри строки слева направо — оба слагаемых при этом уже готовы.

vector<vector<long long>> d(n, vector<long long>(m, 0));
d[0][0] = 1;
for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
        if (i) d[i][j] += d[i - 1][j];
        if (j) d[i][j] += d[i][j - 1];
    }

Проверки if (i) и if (j) заменяют собой возню с граничными условиями. Альтернатива — завести таблицу на строку и столбец больше и считать с единицы; в задачах со сложными переходами так обычно чище.

Препятствия

Пусть часть клеток закрыта. Меняется ровно одна вещь: закрытая клетка получает ноль и ничего никуда не передаёт.

for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
        if (blocked[i][j]) { d[i][j] = 0; continue; }
        if (i == 0 && j == 0) { d[i][j] = 1; continue; }
        if (i) d[i][j] += d[i - 1][j];
        if (j) d[i][j] += d[i][j - 1];
    }

Проверено: на 20 000 случайных досок до $6 \times 6$ с препятствиями совпадает с перебором всех маршрутов.

Порядок проверок важен: препятствие сильнее старта. Если начальная клетка закрыта, ответ ноль, а не единица — и код выше это делает правильно только потому, что blocked проверяется первым.

Стоимость пути

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

const long long INF = 1e18;
vector<vector<long long>> d(n, vector<long long>(m, INF));
d[0][0] = a[0][0];
for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
        if (i == 0 && j == 0) continue;
        long long best = INF;
        if (i) best = min(best, d[i - 1][j]);
        if (j) best = min(best, d[i][j - 1]);
        d[i][j] = best + a[i][j];
    }

Обратите внимание на базу: она изменилась вместе с операцией. Для подсчёта количества базой была единица, для минимума — стоимость самой стартовой клетки, а всё остальное — бесконечность. Это то самое правило про нейтральный элемент.

Порядок обхода читается из формулы

В переходе выше стоят $d[i-1][j]$ и $d[i][j-1]$ — оба индекса только уменьшаются, значит, годится обычный обход сверху вниз и слева направо.

Стоит появиться в задаче ходу влево — и порядок ломается: $d[i][j+1]$ ещё не посчитан. Варианты:

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

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

Что ещё живёт в таблице

задача	$i$	$j$
пути в сетке	строка	столбец
рюкзак	номер предмета	занятый вес
НОП двух строк	префикс первой	префикс второй
разбиение числа на слагаемые	само число	наибольшее слагаемое
подотрезки	левая граница	правая граница

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