Задача 67
Максимальная сумма пути 2

Начиная с вершины представленного ниже треугольника и переходя к прилежащим числам в следующем ряду, максимальная возможная сумма пройденных чисел по пути от вершины до основания равна 23.

3
7 4
2 4 6
8 5 9 3

Т.е., 3 + 7 + 4 + 9 = 23.

Найти максимальную сумму при переходе от вершины до основания треугольника, представленноготекстовым файлом размером 15КБ triangle.txt (щелкнуть правой кнопкой мышии выбрать 'Save Link/Target As...'), в котором содержится треугольник с одной сотней строк.

ПРИМЕЧАНИЕ: Это намного усложненная версия 18-й задачи. Данную задачу нельзя решить, испробовав каждыйвозможный вариант, поскольку всего их 2^(99)! Если бы удалось проверять одинтриллион (10^(12)) вариантов в секунду, потребовалось бы двадцать биллионов летчтобы испробовать их все. Существует эффективный алгоритм решения данной задачи. ;o)

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net