DP по сетке и двум координатам

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

Сколькими путями пройти клетчатую карту

Дана прямоугольная сетка: 0 — свободная клетка, 1 — препятствие. Из (0,0) нужно попасть в правый нижний угол, двигаясь только вниз или вправо. Посчитать количество путей. Для сетки [[0,0,0],[0,1,0],[0,0,0]] ответ 2.

Как разрастаются все маршруты по сетке

Рекурсивно из клетки идти вправо и вниз, останавливаясь за границей и на препятствии. Маршруты до одной клетки имеют общие хвосты: разные пути могут прийти в (r,c), но число продолжений оттуда одинаково. Без кеша это экспоненциальное дерево.

Где разные маршруты приходят в одну клетку

Мы повторяем подсчёт путей до или из одних и тех же координат. Хранить путь как список ходов не нужно: достаточно количества путей для каждой клетки.

Почему путь в клетку приходит сверху или слева

В свободную клетку (r,c) последний ход пришёл либо сверху (r-1,c), либо слева (r,c-1). Значит, dp[r][c] = dp[r-1][c] + dp[r][c-1]. Препятствие получает 0: через него путь не проходит. Стартовая свободная клетка имеет ровно один способ быть достигнутой — начать в ней.

Что означает число путей в клетке

После заполнения очередной клетки dp[r][c] точно равно количеству разрешённых путей из старта в (r,c). Верхняя строка и левая колонка уже корректны, потому что мы идём слева направо внутри строк и сверху вниз по строкам.

В каком порядке заполнять карту путей

1. Если сетка пуста, старт или финиш заблокирован — вернуть 0.
2. Создать rows x cols таблицу нулей и задать dp[0][0] = 1.
3. Для каждой свободной клетки кроме старта сложить готовые верхний и левый ответы, если соседи существуют.
4. Вернуть правый нижний элемент.

Как отразить препятствия в таблице

В этих реализациях grid не меняется. Это важно, если сетка нужна ещё для отображения препятствий или повторного запуска функции.

C++17

#include <cassert>
#include <iostream>
#include <vector>

using namespace std;

long long countPaths(const vector<vector<int>>& grid) {
    if (grid.empty() || grid[0].empty() || grid[0][0] == 1) return 0;
    int rows = static_cast<int>(grid.size());
    int cols = static_cast<int>(grid[0].size());
    vector<vector<long long>> dp(rows, vector<long long>(cols, 0));
    dp[0][0] = 1;

    for (int row = 0; row < rows; ++row) {
        for (int col = 0; col < cols; ++col) {
            if (grid[row][col] == 1 || (row == 0 && col == 0)) continue;
            if (row > 0) dp[row][col] += dp[row - 1][col];
            if (col > 0) dp[row][col] += dp[row][col - 1];
        }
    }
    return dp[rows - 1][cols - 1];
}

int main() {
    assert(countPaths({{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}) == 2);
    assert(countPaths({{1}}) == 0);
    cout << countPaths({{0, 0}, {0, 0}}) << '\n';
}

Python 3

def count_paths(grid: list[list[int]]) -> int:
    if not grid or not grid[0] or grid[0][0] == 1:
        return 0

    rows = len(grid)
    cols = len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = 1

    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == 1 or (row == 0 and col == 0):
                continue
            if row > 0:
                dp[row][col] += dp[row - 1][col]
            if col > 0:
                dp[row][col] += dp[row][col - 1]
    return dp[-1][-1]


assert count_paths([[0, 0, 0], [0, 1, 0], [0, 0, 0]]) == 2
assert count_paths([[1]]) == 0
print(count_paths([[0, 0], [0, 0]]))

Сколько памяти занимает маршрутная таблица

O(rows * cols) времени и столько же памяти. Таблицу можно сжать до одной строки O(cols), если порядок обновления понятен. Число путей быстро растёт: для большой свободной сетки long long переполняется, а в Python число может стать очень большим; условия часто требуют модуль.

Какие клетки немедленно обнуляют ответ

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

На каких картах проверить переход

• пустая сетка и [[1]];
• [[0]] -> 1;
• сетка 2x2 без препятствий -> 2;
• препятствие в середине примера -> 2;
• препятствие на финише -> 0;
• одна строка с препятствием посередине -> 0.

Когда координаты становятся состоянием DP

Сигналы: прямоугольная сетка, разрешены монотонные движения, «сколько путей», «минимальная стоимость до клетки», «дойти до правого нижнего угла». Координаты естественно становятся индексами состояния.

Когда разрешённые ходы требуют другой модели

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

Самопроверка заблокированной клетки

Вопрос: почему препятствие получает dp[row][col] = 0?
Ответ: ни один допустимый путь не может закончиться в заблокированной клетке, поэтому оно не передаёт пути соседям.

Самопроверка сетки 2x2 без препятствий

Вопрос: чему равен ответ для сетки 2x2 без препятствий?
Ответ: 2: вправо-вниз и вниз-вправо. Формула даёт dp[1][1] = 1 + 1.

Потренируйте двухмерную таблицу

Измените задачу на минимальную сумму чисел по пути вправо-вниз. Сначала замените «сумму количеств» на min, затем выберите значение для недостижимой клетки. Подсказка: для минимума полезно infinity, а не ноль.

Самостоятельная карта без подсказок

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

Задача 1

В сетке разрешены ходы вниз, вправо и по диагонали вниз-вправо. Часть клеток заблокирована. Посчитайте число путей из левого верхнего угла в правый нижний.

Что даёт координатное состояние

Двумерное DP — это точный ответ для клетки, а не магическая таблица. Направления разрешённых ходов задают зависимости и порядок вычисления.