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