В числовом треугольнике в строке 0 одно число, в строке 1 два и так далее. Начните с вершины и спускайтесь на одну строку за шаг, каждый раз переходя к числу прямо под текущим или к числу снизу справа (с позиции i на i или i + 1). Найдите путь с наибольшей суммой чисел. При переборе всех путей работа удваивается с каждой строкой, а если считать снизу вверх, начиная с последней строки, сложность остаётся квадратичной.
Реализуйте triangle_max_path_sum(triangle).
Входные данные
triangle: строки сверху вниз; в строке r ровно r + 1 чисел, они могут быть отрицательными.
Выходные данные
Верните наибольшую возможную сумму пути сверху вниз. Для пустого треугольника верните 0.
Ограничения
0 ≤ число строк ≤ 100; −1000 ≤ значение ≤ 1000
Примеры
Ввод:
triangle = [
[4],
[7, 2],
[1, 9, 5],
[6, 3, 8, 2]
]
Ожидаемый вывод:
expected = 28
Ввод:
std::vector<std::vector<long long>> triangle = {
{4},
{7, 2},
{1, 9, 5},
{6, 3, 8, 2}
};
Ожидаемый вывод:
long long expected = 28;
Ввод:
long[][] triangle = new long[][] {
new long[] {4},
new long[] {7, 2},
new long[] {1, 9, 5},
new long[] {6, 3, 8, 2}
};
Ожидаемый вывод:
long expected = 28;
Пояснение
Лучший путь 4, 7, 9, 8 (позиции 0, 0, 1, 2) даёт 28.
Ввод:
triangle = [
[-3],
[5, -8],
[-1, 2, 9]
]
Ожидаемый вывод:
expected = 4
Ввод:
std::vector<std::vector<long long>> triangle = {
{-3},
{5, -8},
{-1, 2, 9}
};
Ожидаемый вывод:
long long expected = 4;
Ввод:
long[][] triangle = new long[][] {
new long[] {-3},
new long[] {5, -8},
new long[] {-1, 2, 9}
};
Ожидаемый вывод:
long expected = 4;
Пояснение
С отрицательными числами путь −3, 5, 2 даёт 4, а −3, −8, 9 даёт −2, поэтому ответ 4.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Начните с нижней строки: лучший путь из нижней клетки равен её значению.
Подсказка 2
Лучший путь из клетки - это её значение плюс больший из лучших путей двух клеток под ней.
Подсказка 3
После обработки всех строк снизу вверх ответ окажется в верхней клетке.
Ожидаемая сложность
время O(rows²), доп. память O(rows)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.