On vous fournit une structure de données représentant un triangle de nombres entiers. Votre tâche est de déterminer la somme minimale des valeurs le long d'un chemin qui part du sommet du triangle et se termine sur l'une des cellules de sa base. La règle de déplacement est la suivante : depuis un élément triangle[i][j] (où i est l'indice de la ligne et j est l'indice de la colonne), vous pouvez vous déplacer uniquement vers l'élément triangle[i+1][j] ou triangle[i+1][j+1] de la ligne suivante. Autrement dit, si vous êtes sur l'indice j de la ligne actuelle, vous pouvez aller à l'indice j ou j + 1 de la ligne suivante.

Exemples Exemple 1 :

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explication: Le chemin ayant la somme minimale est mis en évidence ci-dessous :
   2
  3 4
 6 5 7
4 1 8 3
Le chemin 2 → 3 → 5 → 1 donne une somme totale de 11.

Exemple 2 :

Input: triangle = [[-10]]
Output: -10

Contraintes

• 1 <= triangle.length <= 200
• triangle[0].length == 1
• triangle[i].length == triangle[i - 1].length + 1
• -10^4 <= triangle[i][j] <= 10^4

Approche de Résolution Ce problème est un cas classique de programmation dynamique. L'idée fondamentale est de calculer le coût minimal pour atteindre chaque cellule du triangle à partir du sommet, ou inversement, de calculer le coût minimal pour atteindre la base à partir de chaque cellule. Nous explorerons deux implémentations : une utilisant un tableau 2D pour la table de DP et une autre optimisée en espace utilisant un tableau 1D.

Programmation Dynamique avec Tableau 2D (Approche Top-Down) Nous définissons dpTable[ligne][col] comme la somme minimale pour atteindre l'élément triangle[ligne][col] depuis le sommet. La construction de cette table se fait ligne par ligne, du haut vers le bas.

1. Cas de base : L'élément au sommet du triangle triangle[0][0] est le point de départ. Ainsi, dpTable[0][0] = triangle[0][0].
2. Relations de récurrence : Pour chaque élément triangle[ligne][col] (pour ligne > 0) : - Si col == 0 (premier élément de la ligne), il ne peut provenir que de l'élément directement au-dessus : dpTable\[ligne\]\[0\] = triangle\[ligne\]\[0\] + dpTable\[ligne - 1\]\[0\]. - Si col == ligne (dernier élément de la ligne), il ne peut provenir que de l'élément au-dessus et à gauche : dpTable\[ligne\]\[ligne\] = triangle\[ligne\]\[ligne\] + dpTable\[ligne - 1\]\[ligne - 1\]. - Pour les éléments intermédiaires (0 < col < ligne), l'élément triangle\[ligne\]\[col\] peut être atteint soit depuis triangle\[ligne - 1\]\[col - 1\], soit depuis triangle\[ligne - 1\]\[col\]. La somme mniimale sera donc : dpTable\[ligne\]\[col\] = triangle\[ligne\]\[col\] + min(dpTable\[ligne - 1\]\[col - 1\], dpTable\[ligne - 1\]\[col\]).
3. Résultat final : Une fois la table dpTable entièrement remplie, la somme minimale globale est le plus petit élément de la dernière ligne de dpTable.

#include <vector>
#include <algorithm> // Pour std::min

class SolveTriangle {
public:
    int trouverCheminMinimum(std::vector<std::vector<int>>& triangle) {
        int nombreLignes = triangle.size();
        if (nombreLignes == 0) {
            return 0; // Triangle vide
        }

        // dpTable[ligne][col] stocke la somme minimale pour atteindre triangle[ligne][col]
        std::vector<std::vector<int>> dpTable(nombreLignes);

        // Initialisation de la première ligne de la table DP
        dpTable[0].push_back(triangle[0][0]);

        // Remplir le reste de la table DP, ligne par ligne
        for (int ligne = 1; ligne < nombreLignes; ++ligne) {
            // Chaque ligne 'ligne' du triangle a 'ligne + 1' éléments
            dpTable[ligne].resize(ligne + 1);

            // Gérer le premier élément de la ligne actuelle (colonne 0)
            dpTable[ligne][0] = triangle[ligne][0] + dpTable[ligne - 1][0];

            // Gérer les éléments intermédiaires
            for (int col = 1; col < ligne; ++col) {
                dpTable[ligne][col] = triangle[ligne][col] + std::min(dpTable[ligne - 1][col - 1], dpTable[ligne - 1][col]);
            }

            // Gérer le dernier élément de la ligne actuelle (colonne 'ligne')
            dpTable[ligne][ligne] = triangle[ligne][ligne] + dpTable[ligne - 1][ligne - 1];
        }

        // Le résultat final est le minimum des sommes de la dernière ligne du tableau DP
        int resultatMin = dpTable[nombreLignes - 1][0];
        for (int col = 1; col < nombreLignes; ++col) {
            resultatMin = std::min(resultatMin, dpTable[nombreLignes - 1][col]);
        }

        return resultatMin;
    }
};

Optimisation Spatiale avec Tableau 1D (Approche Bottom-Up) L'approche précédente utilise une complexité spatiale de O(N^2) où N est le nombre de lignes. Nous pouvons l'optimiser à O(N) en utilisant un tableau 1D. Une méthode efficace pour y parvenir avec un triangle est de travailler de la base vers le sommet. Nous définissons cheminMinParElement[j] comme la somme minimale d'un chemin partant de la cellule triangle[ligne][j] et allant jusqu'à la base du triangle.

1. Initialisation : Nous commençons par la dernière ligne du triangle. Le tableau 1D cheminMinParElement est initialisé avec les valeurs de cette dernière ligne, car à partir de ces éléments, le chemin minimal jusqu'à la base est simplement leur propre valeur.
2. Itération : Nous parcourons le triangle en remontant, de l'avant-dernière ligne (nombreLignes - 2) jusqu'à la première ligne (0).
3. Relations de récurrence : Pour chaque élément triangle[ligne][col] de la ligne actuelle, la somme minimale passant par cet élément est sa propre valeur plus le minimum des sommes minimales de ses deux enfants adjacents sur la ligne inférieure. C'est-à-dire : cheminMinParElement[col] = triangle[ligne][col] + min(cheminMinParElement[col], cheminMinParElement[col + 1]). Notez que cheminMinParElement[col] et cheminMinParElement[col + 1] représentent ici les sommes minimales des chemins partant des éléments triangle[ligne + 1][col] et triangle[ligne + 1][col + 1] respectivement.
4. Résultat final : Après avoir traité toutes les lignes jusqu'au sommet, cheminMinParElement[0] contiendra la somme minimale globale du sommet à la base du triangle.

#include <vector>
#include <algorithm> // Pour std::min

class SolveTriangleOptimise {
public:
    int trouverCheminMinimum(std::vector<std::vector<int>>& triangle) {
        int nombreLignes = triangle.size();
        if (nombreLignes == 0) {
            return 0; // Triangle vide
        }

        // Initialiser le tableau DP 1D avec la dernière ligne du triangle
        // cheminMinParElement[j] stockera le chemin minimum depuis (ligne_actuelle, j) jusqu'à la base
        std::vector<int> cheminMinParElement = triangle[nombreLignes - 1];

        // Parcourir le triangle de l'avant-dernière ligne jusqu'au sommet
        for (int ligne = nombreLignes - 2; ligne >= 0; --ligne) {
            // Pour chaque élément de la ligne actuelle
            for (int col = 0; col <= ligne; ++col) {
                // Mettre à jour la somme minimale pour l'élément actuel
                // en ajoutant sa valeur au minimum des chemins de ses deux "enfants" sur la ligne inférieure
                cheminMinParElement[col] = triangle[ligne][col] + std::min(cheminMinParElement[col], cheminMinParElement[col + 1]);
            }
        }

        // Le résultat final est la somme minimale qui part du sommet (premier élément du tableau DP)
        return cheminMinParElement[0];
    }
};