Flashcards : Programmation dynamique : Fibonacci et rendu monnaie — 22 cartes

Suite numérique où chaque terme est la somme des deux précédents.

Appels récursifs répétés avec mêmes paramètres, gaspillage de temps.

Éviter les recalculs en mémorisant résultats intermédiaires.

Stocker résultats pour éviter recalculs redondants.

Récursive, vérifie la mémoire avant de calculer.

Itérative, calcule du plus petit sous-problème vers le grand.

Mémoïsation pour rendre le calcul efficace et sans redondance.

Appels multiples avec mêmes paramètres, inefficace.

Minimiser le nombre de pièces pour une somme donnée.

Minimiser nbre de pièces avec formule : nbre[som] = 1 + min(nbre[som - pi]).

Même sous-problèmes résolus plusieurs fois, inefficace.

Mémoïsation avec cache pour stocker résultats intermédiaires.

Tableau ou liste de taille som+1, initialisé à zéro.

Enregistrer l’indice de la pièce utilisée pour chaque somme.

Reconstruction de la liste pièces via garde après calcul.

Retourne à la fois nombre et composition des pièces.

Pour somme 9, solution optimale : [2,2,5].

fib(n) = fib(n-1) + fib(n-2), avec conditions de base.

Calculer en ordre croissant, stocker dans tableau.

Récursion avec mémoïsation, vérifie cache avant calcul.

Réduction du nombre d’appels, calcul plus rapide.

Mémoïsation est une technique, PD est une stratégie globale.