Вычислять просто сумму крайних правых элементов разве не подойдёт?

Се просто=) начинаем с низу треугольника:
Разбиваем нижние числа на пары, если последнему числу пары нет, то не беда.
Меньшее число в каждой паре заменяем на большее число в каждой паре. Прибавляем к вверху стоящему ряду эти числа(по правилу: к каждому верхнему числу прибавляются числа влево- и вправо-вниз от него по диагонали)
Таким образом "сворачиваем" треугольник пока не дойдем до вершины.
Теперь тупо идем от вершины по самым большим числам. (Например под вершиной стоят числа 120 и 150 - идем вправо, под числом 150 числа 75 и 70 - идем влево и т. д.)
Запоминаем маршрут по свернутому треугольнику и накладываем на несвернутый - маршрут получен.
Теперь программу обмануть не удастся и она всегда выберет нужный маршрут. =)
например треугольник
1
1 2
9 1 1
программа успешно пройдет как надо=)

"источник: Международная олимпиада по информатике, 1994"
а для какого это класса олимпиада то???