Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Maximale Pfadsumme im Zahlendreieck

Finde die größte Summe auf einem Pfad von der Spitze eines Zahlendreiecks bis zur untersten Zeile.

Das lernst du

  • Eine exponentielle Suche durch dynamische Programmierung ersetzen
  • Ergebnisse aus der Zeile darunter kombinieren
  • Negative Werte und leere Eingaben behandeln

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

Beispiel 1
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.

Beispiel 2
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.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.