RU
EN
ES
ZH
FR
DE
PT
AR
HI
Поиск максимального пути в числовом треугольнике
Swift
Сложный
loops
Задача «Поиск максимального пути в числовом треугольнике»
Дан треугольник из целых чисел. Нужно найти максимальную сумму чисел на пути от вершины до основания, двигаясь на каждом шаге на одну строку вниз и на один столбец влево или вправо (в соседние элементы следующей строки). Реализуйте алгоритм, используя циклы и динамическое программирование. Треугольник задается количеством строк N и затем N строками чисел. Выведите одно число – максимальную сумму.
Формат ввода
Первая строка содержит целое число N (1 ≤ N ≤ 100). Далее следуют N строк, в каждой из которых i+1 целых чисел (где i — номер строки, начиная с 0). Числа по модулю не превышают 10^4.
Формат вывода
Одно целое число – максимальная сумма пути.
Примеры
Пример 1
ВВОД
4
5
9 6
4 6 8
0 7 1 5
ВЫВОД
27
Пример 2
ВВОД
1
ВЫВОД
0
Пример 3
ВВОД
3
1
2 3
4 5 6
ВЫВОД
10
Пример 4
ВВОД
2
1 2
3 4
ВЫВОД
4
Пример 5
ВВОД
2
ВЫВОД
0
main.swift