Код Senior Динамическое программирование обновлено
Максимальный путь по треугольнику
Условие
Треугольник из массивов. Идти можно только на соседа снизу. Верни максимальную сумму пути от вершины до основания.
Примеры
maxPathSum([[1], [4, 8], [1, 5, 3]]) // 14
maxPathSum([[1], [-3, -4], [2, 1, 9]]) // 6
maxPathSum([[5]]) // 5
Как подойти
В исходном сборнике для второго примера указан ответ 7, но его там взять неоткуда: лучший путь 1 → −4 → 9 даёт 6. Пересчитать пример руками до написания кода - привычка, которая экономит полчаса отладки. Жадный спуск «иди к большему соседу» неверен: локально лучший шаг может отрезать путь к большой сумме ниже. Динамика снизу вверх решает за O(n²) времени и O(n) памяти, свёрнутых в один массив. Это задача Project Euler 18 и её же дают на собеседованиях.
Подсказки: 3
- Идти сверху вниз означает перебор всех путей.
- Снизу вверх каждая клетка получает максимум из двух нижних соседей.
- Хватает одного массива длиной в основание.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.