ДП по сетке: как избежать off-by-one в базе при подсчёте путей с препятствиями?
Считаю число путей из левого верхнего в правый нижний угол сетки n×m, можно идти вправо и вниз, есть клетки-препятствия. Постоянно путаюсь в инициализации первой строки/столбца и получаю то на 1 больше, то 0. Как правильно задать базу, чтобы препятствия учитывались?
2 ответа
Корень проблемы — база первой строки и столбца обрабатывается как особый случай, и там легко ошибиться с препятствиями. Чище всего ввести рамку-нуль (sentinel-строку и столбец из нулей) и единый переход для всех клеток, кроме старта.
// grid[i][j] == 1 — препятствие, 0 — свободно
vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (grid[i-1][j-1] == 1) { dp[i][j] = 0; continue; } // препятствие
if (i == 1 && j == 1) dp[i][j] = 1; // старт
else dp[i][j] = dp[i-1][j] + dp[i][j-1]; // сверху + слева
}
long long ans = dp[n][m];
Сложность O(n·m). Рамка dp[0][*]=dp[*][0]=0 инициализируется автоматически (вектор из нулей), и переход dp[i-1][j]+dp[i][j-1] корректно работает на краю — лишние слагаемые из рамки равны нулю. Это убирает ручную инициализацию первой строки/столбца, где и сидит off-by-one.
Две частые грабли именно здесь. Первая — старт или финиш на препятствии: если grid[0][0]==1 или grid[n-1][m-1]==1, ответ ровно 0; код выше это ловит автоматически (старт-клетка обнулится continue). Вторая — переполнение: число путей растёт как биномиальный коэффициент, для сетки 40×40 это ~10^23, никакой long long не хватит — либо считай по модулю (dp[i][j] %= MOD), как обычно требуют в условии, либо большие числа. Если в условии есть «по модулю 10^9+7», не забудь % MOD на каждом сложении.