Triangle

Средняя№120снизу вверх

Числа сложены треугольником: одно в первой строке, два во второй и так далее. Нужно пройти от вершины до нижней строки; из клетки можно шагнуть в любую из двух клеток прямо под ней. Найти наименьшую сумму чисел на таком пути. Наш пример: [2], [4, 1], [3, 8, 9], [1, 6, 7, 2], ответ 10.

120 TriangleРазбор · 1×

Пример: треугольник из 4 строк. Единица в строке 1 кажется лучшим началом, но всё под ней дорогое: снизу вверх у неё выходит 12, а у четвёрки рядом — 8.

треугольникbest22441133889911667722
число треугольникасамый дешёвый путь вниз из клеткиэтот шагберём отсюдасамый дешёвый путь

best — копия треугольника. Нижняя строка уже верна: из её клетки путь вниз — это сама клетка

01/23
сначала · назад · пуск · шаг
Скорость
1function minimumTotal(tri):
2 best = copy of tri
3 for r from len(tri) - 2 down to 0:
4 for c from 0 to r:
5 left = best[r + 1][c]
6 right = best[r + 1][c + 1]
7 best[r][c] = tri[r][c] + min(left, right)
8 return best[0][0]
состояние
best
[[2], [4, 1], [3, 8, 9], [1, 6, 7, 2]]
r
–
c
–
left
–
right
–
историянажмите шаг, чтобы вернуться

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

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

  1. Из клетки самый дешёвый путь вниз — её число плюс меньший из самых дешёвых путей из двух клеток под ней. Если идти по строкам снизу, эти две всегда уже готовы.
  2. Каждая клетка нижней строки — уже законченный путь, поэтому в копии треугольника там сразу верные значения, и других базовых случаев не нужно.
  3. Выбирать на спуске клетку подешевле — значит смотреть только на строку вперёд: здесь так берут 1 и платят 17. Каждая клетка best уже учла все пути под собой.

Сложность

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

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

Решить на LeetCode ↗

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