1.1 Énoncé

Étant donné un ensemble de valeurs de pièces différentes et un montant cible, implémentez une fonction pour calculer le nombre minimum de pièces nécessaires pour atteindre ce montant. Si aucune combinaison de pièces ne permet d'atteindre le montant, retournez -1. Vous pouvez supposer que chaque type de pièce est disponible en quantité illimitée. Exemple 1 :

Entrée : valeursPieces = [1, 2, 5], montant = 11
Sortie : 3
Explication : 11 = 5 + 5 + 1

Exemple 2 :

Entrée : valeursPieces = [2], montant = 3
Sortie : -1

Exemple 3 :

Entrée : valeursPieces = [1], montant = 0
Sortie : 0

Contraintes :

• 1 <= valeursPieces.length <= 12
• 1 <= valeursPieces[i] <= 2^31 - 1
• 0 <= montant <= 10^4

2. Analyse du problème

Il s'agit d'un problème classique de programmation dynamique, analogue au problème du sac à dos complet. Les défis principaux sont : - Pièces en quantité illimitée : Chaque type de pièce peut être utilisé plusieurs fois.

• Minimiser le nombre de pièces : L'objectif est de trouver la combinaison avec le minimum de pièces.
• Cas sans solution : Si le montant ne peut pas être atteint, il faut retourner -1.

Pour un développeur frontend, la compréhension de ce problème aide à gérer des scénarios comme l'optimisation des ressources ou la gestion d'états complexes nécessitant le calcul de solutions optimales. ### 3. Approche de résolution

3.1 Aperçu des approches

Plusieurs approches existent : la récursion naïve, la récursion avec mémorisation (programmation dynamique descendante) et la programmation dynamique ascendante. L'approche optimale est la programmation dynamique ascendante car elle élimine le coût de la récursion et offre les meilleures complexités temporelle et spatiale. #### 3.2 Détail des approches

• Récursion naïve : Tente toutes les combinaisons possibles de manière récursive. Conduit à une complexité temporelle exponentielle.
• Récursion avec mémorisation : Ajoute un cache pour stocker les résultats des sous-problèmes déjà calculés. Réduit la complexité à un niveau polynomial.
• Programmation dynamique ascendante : Calcule itérativement le nombre minimum de pièces pour chaque montant de 0 à montant cible. C'est l'approche recommandée.

Solution optimale : Programmation dynamique ascendante avec une complexité O(montant × n) en temps et O(montant) en espace, où n représente le nombre de types de pièces.

4. Implémentation

4.1 Approche récursive naïve

/**
 * Approche par récursion naïve
 * @param {number[]} valeursPieces - Tableau des valeurs de pièces
 * @param {number} montant - Montant cible
 * @return {number} - Nombre minimum de pièces ou -1
 */
function calculerMonnaie(valeursPieces, montant) {
    // Fonction récursive interne avec reste représente le montant restant
    function resoudre(reste) {
        // Cas de base : montant négatif indique aucune solution
        if (reste < 0) return -1;
        // Cas de base : montant atteint, aucune pièce supplémentaire nécessaire
        if (reste === 0) return 0;

        let minimum = Infinity; // Initialisation du minimum à l'infini
        // Parcours de chaque type de pièce
        for (const valeur of valeursPieces) {
            // Calcul récursif du sous-problème
            const resultat = resoudre(reste - valeur);
            if (resultat !== -1) {
                // Mise à jour du minimum si une solution existe
                minimum = Math.min(minimum, resultat + 1);
            }
        }
        // Retourne -1 si aucune solution trouvée, sinon le minimum
        return minimum === Infinity ? -1 : minimum;
    }

    return resoudre(montant);
}

// Tests
console.log(calculerMonnaie([1, 2, 5], 11)); // Résultat: 3
console.log(calculerMonnaie([2], 3));        // Résultat: -1

4.2 Récursion avec mémorisation (programmation dynamique descendante)

/**
 * Approche par mémorisation (programmation dynamique descendante)
 * @param {number[]} valeursPieces - Tableau des valeurs de pièces
 * @param {number} montant - Montant cible
 * @return {number} - Nombre minimum de pièces ou -1
 */
function calculerMonnaie(valeursPieces, montant) {
    // Tableau de mémorisation des résultats déjà calculés
    const cache = new Array(montant + 1).fill(undefined);

    /**
     * Fonction récursive avec mémorisation
     * @param {number} reste - Montant restant
     * @return {number} - Nombre minimum de pièces ou -1
     */
    function resoudre(reste) {
        if (reste < 0) return -1;
        if (reste === 0) return 0;

        // Retour direct si déjà calculé
        if (cache[reste] !== undefined) return cache[reste];

        let minimum = Infinity;
        for (const valeur of valeursPieces) {
            const resultat = resoudre(reste - valeur);
            if (resultat !== -1) {
                minimum = Math.min(minimum, resultat + 1);
            }
        }

        // Stockage du résultat dans le cache
        cache[reste] = minimum === Infinity ? -1 : minimum;
        return cache[reste];
    }

    return resoudre(montant);
}

// Tests
console.log(calculerMonnaie([1, 2, 5], 11)); // Résultat: 3
console.log(calculerMonnaie([2], 3));        // Résultat: -1

4.3 Programmation dynamique ascendante (solution optimale)

/**
 * Approche par programmation dynamique ascendante
 * @param {number[]} valeursPieces - Tableau des valeurs de pièces
 * @param {number} montant - Montant cible
 * @return {number} - Nombre minimum de pièces ou -1
 */
function calculerMonnaie(valeursPieces, montant) {
    // tableMemo[i] représente le nombre minimum de pièces pour le montant i
    // Initialisation à Infinity indiquant l'inaccessibilité
    const tableMemo = new Array(montant + 1).fill(Infinity);
    tableMemo[0] = 0; // Cas de base : 0 pièce pour le montant 0

    // Itération sur tous les montants de 1 à montant cible
    for (let somme = 1; somme <= montant; somme++) {
        // Parcours de chaque type de pièce
        for (const valeur of valeursPieces) {
            // Vérification de la validité de l'utilisation de la pièce
            if (somme - valeur >= 0) {
                // Transition d'état : minimum entre l'état actuel et nouveau calcul
                tableMemo[somme] = Math.min(tableMemo[somme], tableMemo[somme - valeur] + 1);
            }
        }
    }

    // Retour du résultat ou -1 si impossible
    return tableMemo[montant] === Infinity ? -1 : tableMemo[montant];
}

// Tests
console.log(calculerMonnaie([1, 2, 5], 11)); // Résultat: 3
console.log(calculerMonnaie([2], 3));        // Résultat: -1

5. Comparaison des complexitées

Note : n représente le nombre de types de pièces. La programmation dynamique ascendante est recommandée pour les applications frontend sensibles aux performances.

6. Conclusion

6.1 Modèle de résolution

Pour les problèmes de programmation dynamique impliquant l'optimisation avec des éléments réutilisables, suivez ce modèle : 1. Définir l'état : Utilisez tableMemo[i] pour représenter la solution optimale pour la valeur i. 2. Initialiser : Définissez les cas de base comme tableMemo[0] = 0. 3. Établir la transition : Trouvez la relation entre l'état actuel et les sous-problèmes. 4. Calculer itérativement : Progression des sous-problèmes vers la solution finale. 5. Retourner le résultat : Vérifiez l'existence d'une solution valide.

6.2 Problèmes similaires

• LeetCode 518. Nombre de combinaisons : Compte le nombre de combinaisons possibles au lieu du minimum.
• LeetCode 279. Carrés parfaits : Trouve le minimum de carrés parfaits dont la somme égale n.
• LeetCode 377. Somme de combinaisons IV : Compte les permutations avec éléments réutilisables.
• LeetCode 416. Partition en sous-ensembles égaux : Variante du problème du sac à dos.