Задача на треугольник Опции

[MARSHALL MATHERS]

На рисунке изображен треугольник(я напишу треугольник как он дан в массиве):
|7 |
|38 |
|810 |
|2744 |
|45265|
(типа того, палочками обочначены границы конкретно этого треугольника)
Написать прогу, которая вычисляет наибольшую сумму чисел, расположенных на пути, начинающимся в верхней точке треугольника и заканчивющиймся на основании треугольника. Каждый шаг на пути может осуществлятся вниз по диогонали влево или по диогонали вправо. Число строк в треуголнике >1 и <=100. Треугольник составлен из целых чисел от 0 до 99...(это оригинальый текст задачи) надаюсь на ваши советы?!

[Atos]

Не согласен!
можно и графами обойтись.

На вскидку - кажется можно решить задачу используя Флойда, заменив там знак для поиска максимального веса для пути.
Только граф из треугольника получи и все.

Получишь сложность алгоримта O(n^3).

А у приведённого алгоритма O(n^2), каждая вершина рассматривается только один раз.
Разве можно проще сделать?