Minimum Path Sum

Средняя№64двумерная таблица

В каждой клетке сетки записана цена. Нужно пройти из левого верхнего угла в правый нижний, шагая только вправо или вниз, и заплатить за каждую клетку на пути, оба угла тоже. Найти наименьшую сумму. Наш пример: [3, 1, 5, 1], [2, 6, 4, 2], [1, 1, 3, 2], ответ 12.

64 Minimum Path SumРазбор · 1×

Пример: сетка 3 × 4. Первый шаг вправо стоит всего 1, но самый дешёвый путь идёт вниз по левому столбцу; последняя клетка берёт 10 слева, а не 12 сверху.

0123012+3+1+5+1+2+6+4+2+1+1+3+2
ещё не заполнено: +ценасамая дешёвая сумма до клеткиэтот шагберём отсюдасамый дешёвый путь

Пустая таблица размером с сетку; пока клетка не заполнена, в ней видна её цена

01/40
сначала · назад · пуск · шаг
Скорость
1function minPathSum(grid):
2 dp = table of the grid's size
3 for r from 0 to rows - 1:
4 for c from 0 to cols - 1:
5 if r == 0 and c == 0:
6 dp[r][c] = grid[r][c]
7 continue
8 up = dp[r - 1][c] if r > 0 else infinity
9 left = dp[r][c - 1] if c > 0 else infinity
10 dp[r][c] = min(up, left) + grid[r][c]
11 return dp[rows - 1][cols - 1]
состояние
dp
[[–, –, –, –], [–, –, –, –], [–, –, –, –]]
r
–
c
–
up
–
left
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Любой путь в (r, c) приходит из (r - 1, c) или из (r, c - 1). Самый дешёвый из них — самый дешёвый путь в лучшую из этих двух клеток плюс цена (r, c), поэтому хватает min из двух готовых клеток.
  2. В клетку верхней строки или левого столбца ведёт один вход; недостающая сторона считается ∞, поэтому min всегда берёт настоящую.
  3. Брать на каждом шаге клетку подешевле мало: здесь 1 справа от старта ведёт к сумме 14, а таблица находит 12, начиная шагом вниз.

Сложность

Время O(m × n): каждая клетка — один min и одно сложение. Память O(m × n) на таблицу; клетка читает только свою строку и строку над ней, так что хватит одной строки из n клеток, а можно писать прямо в сетку.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.