Глава 25. Путь с максимальной суммой в числовом треугольнике

Эту задачу мы позаимствовали с сайта Project Euler (задачи № 18 и № 67). Дан числовой треугольник. Мысленно пройдёмся по числам в треугольнике, начиная с вершины, к какому-нибудь числу из нижнего ряда, суммируя числа, встречающиеся на пути. Разрешается шагать или к левому или к правому соседнему числу, расположенному одним этажом ниже. Требуется найти наибольшую сумму (среди всех таких путей). Например, для треугольника на рисунке максимальная сумма равна $23$, а соответствующий путь выделен красным: $$\begin{array}{cccc}& & & \mathbf{3}\\ & & \mathbf{7}& & 4\\ & 2& & \mathbf{4}& & 6\\ 8& & 5& & \mathbf{9}& & 3\end{array}$$

Треугольник с числами программа maxpathsum.pl считывает со стандартного ввода:

% ./maxpathsum.pl
3
7 4
2 4 6
8 5 9 3
␄
23

Конечно, отлаживать программу, каждый раз вводя все эти числа, невозможно. Предлагаем файлы с уже готовыми треугольниками (4, 15, 100 строк), из которых можно перенаправить стандартный ввод:

% ./maxpathsum.pl <maxpathsum-4.txt
23
% ./maxpathsum.pl <maxpathsum-15.txt
1074
% ./maxpathsum.pl <maxpathsum-100.txt
7273