Tous les défis
Moyen 0 résolus 0 % de réussite

Chemin de somme maximale dans un triangle

Trouver la plus grande somme le long d'un chemin allant du sommet d'un triangle de nombres jusqu'à sa dernière ligne.

Ce que vous allez apprendre

  • Remplacer une recherche exponentielle par de la programmation dynamique
  • Combiner les résultats de la ligne du dessous
  • Gérer les valeurs négatives et l'entrée vide

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

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

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

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.