Tutte le sfide
Media 0 risolte 0% di accettazione

Percorso di somma massima in un triangolo

Trova la somma più grande lungo un percorso dalla cima di un triangolo di numeri fino alla sua ultima riga.

Cosa imparerai

  • Sostituire una ricerca esponenziale con la programmazione dinamica
  • Combinare i risultati della riga sottostante
  • Gestire valori negativi e input vuoti

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

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

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

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.