Problème
Un triangle de nombres contient une valeur sur la ligne 0, deux sur la ligne 1, et ainsi de suite. Partez du sommet et descendez d'une ligne à la fois, à chaque fois vers la valeur juste en dessous ou vers celle en dessous à droite (de la position i à i ou i + 1). Trouvez le chemin dont la somme des valeurs est la plus grande. Essayer tous les chemins double le travail à chaque ligne ; remonter depuis la dernière ligne garde un coût quadratique.
Implémentez triangle_max_path_sum(triangle).
Entrée
triangle : les lignes, du haut vers le bas ; la ligne r contient r + 1 valeurs, éventuellement négatives.
Sortie
Renvoyez la plus grande somme possible d'un chemin du sommet jusqu'en bas. Un triangle vide renvoie 0.
Contraintes
0 ≤ lignes ≤ 100 ; −1000 ≤ valeur ≤ 1000
Exemples
Entrée :
triangle = [
[4],
[7, 2],
[1, 9, 5],
[6, 3, 8, 2]
]
Sortie attendue :
expected = 28
Entrée :
std::vector<std::vector<long long>> triangle = {
{4},
{7, 2},
{1, 9, 5},
{6, 3, 8, 2}
};
Sortie attendue :
long long expected = 28;
Entrée :
long[][] triangle = new long[][] {
new long[] {4},
new long[] {7, 2},
new long[] {1, 9, 5},
new long[] {6, 3, 8, 2}
};
Sortie attendue :
long expected = 28;
Explication
Le meilleur chemin est 4, 7, 9, 8 (positions 0, 0, 1, 2), soit 28.
Entrée :
triangle = [
[-3],
[5, -8],
[-1, 2, 9]
]
Sortie attendue :
expected = 4
Entrée :
std::vector<std::vector<long long>> triangle = {
{-3},
{5, -8},
{-1, 2, 9}
};
Sortie attendue :
long long expected = 4;
Entrée :
long[][] triangle = new long[][] {
new long[] {-3},
new long[] {5, -8},
new long[] {-1, 2, 9}
};
Sortie attendue :
long expected = 4;
Explication
Avec des valeurs négatives, −3, 5, 2 donne 4 alors que −3, −8, 9 donne −2, donc la réponse est 4.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Partez de la dernière ligne : le meilleur chemin depuis une case du bas, c'est simplement sa valeur.
Indice 2
Le meilleur chemin depuis une case vaut sa valeur plus le meilleur des deux résultats des cases situées en dessous.
Indice 3
Une fois toutes les lignes traitées en remontant, la case du sommet contient la réponse.
Complexité attendue
temps O(rows²), espace supplémentaire O(rows)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.