Дано числовий трикутник з N рядків. Написати програму, яка обчислює максимальну суму
чисел, розміщених на шляху, що розпочинається із верхнього числа й закінчується
на будь-якому числі в основі трикутника (максимум суми серед усіх таких
шляхів). На кожному кроці до сусіднього по діагоналі числа можна рухатись лише
вліво-вниз або вправо-вниз.
Ідея розв’язання. Задача є
класичною задачею динамічного програмування. Найбільш ефективним є використання
двох одновимірних масивів, в одному з яких буде міститись поточний рядок
«максимальної» суми, а в другому – значення попереднього рядка.
Малюнок, який ілюструє роботу
програми для випадку n=5