FR
RU
EN
ES
ZH
DE
PT
AR
HI
Recherche du chemin maximal dans un triangle numérique
Swift
Hard
loops
Tâche «Recherche du chemin maximal dans un triangle numérique»
Étant donné un triangle d'entiers. Il faut trouver la somme maximale des nombres sur un chemin allant du sommet à la base, en se déplaçant à chaque étape d'une ligne vers le bas et d'une colonne vers la gauche ou la droite (vers les éléments voisins de la ligne suivante). Implémentez un algorithme en utilisant des boucles et la programmation dynamique. Le triangle est défini par le nombre de lignes N, puis par N lignes de nombres. Affichez un seul nombre – la somme maximale.
Format d\ entrée
La première ligne contient un entier N (1 ≤ N ≤ 100). Ensuite, suivent N lignes, chacune contenant i+1 entiers (où i est le numéro de la ligne, en commençant par 0). Les nombres en valeur absolue ne dépassent pas 10^4.
Format de sortie
Un seul entier – la somme maximale du chemin.
Exemples
Exemple 1
ENTRÉE
4
5
9 6
4 6 8
0 7 1 5
SORTIE
27
Exemple 2
ENTRÉE
1
SORTIE
0
Exemple 3
ENTRÉE
3
1
2 3
4 5 6
SORTIE
10
Exemple 4
ENTRÉE
2
1 2
3 4
SORTIE
4
Exemple 5
ENTRÉE
2
SORTIE
0
main.swift