Задача 5: Минимальная сумма пути в треугольнике

Условие

Дан треугольник (в виде списка списков, где triangle[i] — это строка с i + 1 элементом).

Найди минимальную сумму пути от вершины треугольника до его основания.

На каждом шаге можно переместиться на соседнее число в строке ниже:

• Если ты находишься на индексе i в текущей строке, ты можешь перейти на индекс i или i + 1 в следующей строке.

Требование: алгоритмическая сложность решения не должна превышать O(n^2).

---

Примеры

Входные данные	Треугольник	Минимальный путь	Результат
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]	[2] [3,4] [6,5,7] [4,1,8,3]	2 → 3 → 5 → 1	11
triangle = [[-1],[2,3],[1,-1,-3],[4,2,1,3]]	[-1] [2,3] [1,-1,-3] [4,2,1,3]	-1 → 3 → -3 → 1	0

---

Примечание по задаче 2:

При решении этой задачи у меня не получилось получить ответ из предложенных вариантов, поэтому я выбрал его наугад. Окончательный ответ - 150.