DE
RU
EN
ES
ZH
FR
PT
AR
HI
Suche nach dem maximalen Pfad im Zahlendreieck
Swift
Hard
loops
Aufgabe «Suche nach dem maximalen Pfad im Zahlendreieck»
Gegeben ist ein Dreieck aus ganzen Zahlen. Es soll die maximale Summe der Zahlen auf einem Pfad von der Spitze zur Basis gefunden werden, wobei man in jedem Schritt eine Zeile nach unten und einen Schritt nach links oder rechts (zu den benachbarten Elementen der nächsten Zeile) geht. Implementieren Sie den Algorithmus unter Verwendung von Schleifen und dynamischer Programmierung. Das Dreieck wird durch die Anzahl der Zeilen N und dann N Zeilen mit Zahlen angegeben. Geben Sie eine Zahl aus – die maximale Summe.
Eingabeformat
Die erste Zeile enthält eine ganze Zahl N (1 ≤ N ≤ 100). Danach folgen N Zeilen, in denen jeweils i+1 ganze Zahlen stehen (wobei i die Zeilennummer ist, beginnend bei 0). Die Zahlen überschreiten im Betrag nicht 10^4.
Ausgabeformat
Eine ganze Zahl – die maximale Pfadsumme.
Beispiele
Beispiel 1
EINGABE
4
5
9 6
4 6 8
0 7 1 5
AUSGABE
27
Beispiel 2
EINGABE
1
AUSGABE
0
Beispiel 3
EINGABE
3
1
2 3
4 5 6
AUSGABE
10
Beispiel 4
EINGABE
2
1 2
3 4
AUSGABE
4
Beispiel 5
EINGABE
2
AUSGABE
0
main.swift