Все задачи
Средне Решено: 0 Процент решений: 0%

Максимальная сумма пути в треугольнике

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

Чему вы научитесь

  • Заменять экспоненциальный перебор динамическим программированием
  • Объединять результаты из нижней строки
  • Обрабатывать отрицательные значения и пустой вход

Условие

В числовом треугольнике в строке 0 одно число, в строке 1 два и так далее. Начните с вершины и спускайтесь на одну строку за шаг, каждый раз переходя к числу прямо под текущим или к числу снизу справа (с позиции i на i или i + 1). Найдите путь с наибольшей суммой чисел. При переборе всех путей работа удваивается с каждой строкой, а если считать снизу вверх, начиная с последней строки, сложность остаётся квадратичной.

Реализуйте triangle_max_path_sum(triangle).

Входные данные

triangle: строки сверху вниз; в строке r ровно r + 1 чисел, они могут быть отрицательными.

Выходные данные

Верните наибольшую возможную сумму пути сверху вниз. Для пустого треугольника верните 0.

Ограничения

0 ≤ число строк ≤ 100; −1000 ≤ значение ≤ 1000

Примеры

Пример 1
Ввод:
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.

Пример 2
Ввод:
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. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.