Начиная с вершины представленного ниже треугольника и переходя к прилежащим числам в следующем ряду, максимальная возможная сумма пройденных чисел по пути от вершины до основания равна 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⁹⁹! Если бы удалось проверять один триллион (10¹²) вариантов в секунду, потребовалось бы двадцать биллионов лет, чтобы испробовать их все. Существует эффективный алгоритм решения данной задачи. ;o)