Programmation dynamique : Fibonacci et rendu monnaie

📋 Plan du Cours

1. Problème de redondance dans le calcul récursif de la suite de Fibonacci
2. Principe et utilité de la programmation dynamique par mémorisation
3. Formes Top Down et Bottom Up de la programmation dynamique
4. Application de la programmation dynamique Top Down au calcul de Fibonacci
5. Formulation récursive du problème du rendu de monnaie minimal
6. Analyse des appels récursifs redondants dans le rendu de monnaie
7. Utilisation de la programmation dynamique Top Down pour le rendu de monnaie
8. Construction et rôle de la mémoire cache dans le rendu de monnaie
9. Détermination du nombre minimal de pièces et des pièces utilisées
10. Algorithme modifié pour retourner la liste des pièces optimales
11. Exemple pratique d’application du rendu de monnaie optimal

📖 1. Problème de redondance dans le calcul récursif de la suite de Fibonacci

🔑 Notions clés & Définitions

• Suite de Fibonacci : Une suite numérique où chaque terme est défini par 0 pour n=0, 1 pour n=1, et la somme des deux termes précédents pour tout n supérieur ou égal à 2.

📝 Points essentiels

• Le calcul récursif naïf de Fibonacci entraîne de nombreux appels redondants avec les mêmes paramètres, comme plusieurs appels avec n=2 ou n=3 pour n=5.
• Pour n=5, la fonction fibo est appelée plusieurs fois avec les mêmes valeurs, par exemple 3 appels avec n=2.
• Ce problème de redondance s'aggrave rapidement avec l'augmentation de n, entraînant un gaspillage de temps et de mémoire.