Почему это работает
- Пути в свободную клетку — это пути в клетку сверху плюс пути в клетку слева, как и без камней: последний шаг приходит из одной из них.
- В камне 0, поэтому он ничего не добавляет клеткам за ним. Одно это убирает все пути через камень, и ни один путь не нужно проверять отдельно.
- Края больше не сплошные единицы: в верхнюю строку ведёт только прямая линия, а после камня она обрывается, поэтому в (0, 3) — 0.
Сложность
Время O(m × n): каждая клетка — одна проверка и одно сложение. Память O(m × n) на таблицу, или одна строка из n клеток: клетка читает только свою строку и строку над ней.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗