i (с нуля) ровно i + 1 чисел, pyramid[i][j] — плата за то, чтобы встать на клетку j этой строки.
Вы стартуете на вершине pyramid[0][0] и спускаетесь по одной строке за шаг до самого низа. С клетки j можно шагнуть на клетку j или j + 1 строки ниже. Стоимость спуска — сумма всех чисел на пути, включая вершину и клетку в нижней строке.
Верните минимальную стоимость спуска.
Попробуйте обойтись O(n) дополнительной памяти, где n — число строк.pyramid=[[3], [7, 1], [2, 9, 4], [8, 5, 6, 1]] → 9
Выгоднее всего 3 → 1 → 4 → 1, сумма 9. Жадный выбор не всегда помогает: путь через 7 и 2 даёт уже 3 + 7 + 2 + 5 = 17.
pyramid=[[-2], [5, -6]] → -8
Из вершины спускаемся на −6: −2 + (−6) = −8.
pyramid=[[4]] → 4
pyramid=[[3], [7, 1], [2, 9, 4], [8, 5, 6, 1]]
9
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 90 тестов на сервере, включая скрытые.