Problem
Ein Zahlendreieck hat in Zeile 0 einen Wert, in Zeile 1 zwei und so weiter. Du beginnst an der Spitze und gehst Zeile für Zeile nach unten, jeweils zum Wert direkt darunter oder zu dem rechts darunter (von Position i zu i oder i + 1). Finde den Pfad mit der größten Summe. Wer alle Pfade ausprobiert, verdoppelt den Aufwand mit jeder Zeile. Arbeitet man dagegen von der untersten Zeile nach oben, bleibt der Aufwand quadratisch.
Implementiere triangle_max_path_sum(triangle).
Eingabe
triangle: Die Zeilen von oben nach unten. Zeile r hat r + 1 Werte, die auch negativ sein können.
Ausgabe
Gib die größtmögliche Summe eines Pfades von oben nach unten zurück. Für ein leeres Dreieck ist das Ergebnis 0.
Einschränkungen
0 ≤ Zeilen ≤ 100; −1000 ≤ Wert ≤ 1000
Beispiele
Eingabe:
triangle = [
[4],
[7, 2],
[1, 9, 5],
[6, 3, 8, 2]
]
Erwartete Ausgabe:
expected = 28
Eingabe:
std::vector<std::vector<long long>> triangle = {
{4},
{7, 2},
{1, 9, 5},
{6, 3, 8, 2}
};
Erwartete Ausgabe:
long long expected = 28;
Eingabe:
long[][] triangle = new long[][] {
new long[] {4},
new long[] {7, 2},
new long[] {1, 9, 5},
new long[] {6, 3, 8, 2}
};
Erwartete Ausgabe:
long expected = 28;
Erläuterung
Der beste Pfad ist 4, 7, 9, 8 (Positionen 0, 0, 1, 2) mit der Summe 28.
Eingabe:
triangle = [
[-3],
[5, -8],
[-1, 2, 9]
]
Erwartete Ausgabe:
expected = 4
Eingabe:
std::vector<std::vector<long long>> triangle = {
{-3},
{5, -8},
{-1, 2, 9}
};
Erwartete Ausgabe:
long long expected = 4;
Eingabe:
long[][] triangle = new long[][] {
new long[] {-3},
new long[] {5, -8},
new long[] {-1, 2, 9}
};
Erwartete Ausgabe:
long expected = 4;
Erläuterung
Mit negativen Werten ergibt −3, 5, 2 die Summe 4, −3, −8, 9 dagegen nur −2, also lautet die Antwort 4.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Beginne in der untersten Zeile: Der beste Pfad ab einem Feld dort ist einfach sein Wert.
Hinweis 2
Der beste Pfad ab einem Feld ist sein Wert plus das größere der beiden besten Ergebnisse direkt darunter.
Hinweis 3
Wenn du dich Zeile für Zeile nach oben gearbeitet hast, steht in der Spitze das Ergebnis.
Erwartete Komplexität
Zeit O(rows²), zusätzlicher Speicher O(rows)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.