Problema
Un triangolo di numeri ha un valore nella riga 0, due nella riga 1 e così via. Parti dalla cima e scendi di una riga alla volta, ogni volta verso il valore subito sotto oppure verso quello sotto a destra (dalla posizione i alla i oppure alla i + 1). Trova il percorso con la somma dei valori più grande. Provare tutti i percorsi raddoppia il lavoro a ogni riga; risalire a partire dall'ultima riga mantiene il costo quadratico.
Implementa triangle_max_path_sum(triangle).
Input
triangle: le righe dall'alto in basso; la riga r ha r + 1 valori, che possono essere negativi.
Output
Restituisci la somma più grande possibile di un percorso dalla cima al fondo. Per un triangolo vuoto restituisci 0.
Vincoli
0 ≤ righe ≤ 100; −1000 ≤ valore ≤ 1000
Esempi
Input:
triangle = [
[4],
[7, 2],
[1, 9, 5],
[6, 3, 8, 2]
]
Output atteso:
expected = 28
Input:
std::vector<std::vector<long long>> triangle = {
{4},
{7, 2},
{1, 9, 5},
{6, 3, 8, 2}
};
Output atteso:
long long expected = 28;
Input:
long[][] triangle = new long[][] {
new long[] {4},
new long[] {7, 2},
new long[] {1, 9, 5},
new long[] {6, 3, 8, 2}
};
Output atteso:
long expected = 28;
Spiegazione
Il percorso migliore è 4, 7, 9, 8 (posizioni 0, 0, 1, 2), per un totale di 28.
Input:
triangle = [
[-3],
[5, -8],
[-1, 2, 9]
]
Output atteso:
expected = 4
Input:
std::vector<std::vector<long long>> triangle = {
{-3},
{5, -8},
{-1, 2, 9}
};
Output atteso:
long long expected = 4;
Input:
long[][] triangle = new long[][] {
new long[] {-3},
new long[] {5, -8},
new long[] {-1, 2, 9}
};
Output atteso:
long expected = 4;
Spiegazione
Con i negativi, −3, 5, 2 dà 4 mentre −3, −8, 9 dà −2, quindi la risposta è 4.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Parti dall'ultima riga: il miglior percorso da una cella in fondo è semplicemente il suo valore.
Suggerimento 2
Il miglior percorso da una cella è il suo valore più il maggiore tra i migliori delle due celle sottostanti.
Suggerimento 3
Dopo aver elaborato tutte le righe risalendo, la cella in cima contiene la risposta.
Complessità attesa
tempo O(rows²), spazio aggiuntivo O(rows)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.