> La programmation dynamique est une méthode algorithmique permettant de résoudre efficacement des problèmes complexes en mémorisant les résultats des sous-problèmes déjà résolus.
`fibonacci(3)` est calculé **2 fois**, `fibonacci(2)` est calculé **3 fois**, `fibonacci(1)` est calculé **5 fois**.
La complexité de cet algorithme est **exponentielle** : O(2ⁿ). Pour `fibonacci(50)`, cela représente plus de 1 000 milliards d'appels !
**L'idée clé** : si on avait mémorisé le résultat de `fibonacci(3)` lors du premier calcul, on n'aurait pas eu besoin de le recalculer.
---
### L'idée clé : la programmation dynamique
> **Définition** : La **programmation dynamique** est une méthode algorithmique qui consiste à :
>
> 1. Décomposer un problème en **sous-problèmes** plus simples
> 2. **Mémoriser** le résultat de chaque sous-problème pour éviter de le recalculer
> 3. Combiner les résultats pour résoudre le problème initial
Il existe deux façons de mettre en œuvre cette idée :
| Approche | Principe | Autre nom |
|----------|----------|-----------|
| **Top-down** | On part du problème initial et on descend vers les sous-problèmes, en mémorisant au passage | Mémoïsation |
| **Bottom-up** | On commence par les sous-problèmes les plus simples et on remonte vers le problème initial | Tabulation |
---
### Approche Top-Down : la mémoïsation
On garde la structure récursive, mais on ajoute un **dictionnaire** pour mémoriser les résultats déjà calculés. Avant chaque calcul, on vérifie si le résultat n'est pas déjà connu.
```python
def fibonacci_memo(n):
memo = {}
memo[0] = 0
memo[1] = 1
def fib(k):
if k in memo: # si déjà calculé, on retourne directement
return memo[k]
memo[k] = fib(k-1) + fib(k-2) # sinon, on calcule et on mémorise
return memo[k]
return fib(n)
```
Avec `fibonacci_memo(5)`, chaque valeur n'est calculée qu'**une seule fois** :
```
fib(5) → calcule fib(4) et fib(3)
fib(4) → calcule fib(3) et fib(2)
fib(3) → calcule fib(2) et fib(1) = 1 ✓ (mémorisé)
Chaque case est calculée exactement une fois, dans l'ordre. Complexité : **O(n)** en temps, O(n) en mémoire.
> **Remarque** : On peut même optimiser l'espace mémoire à O(1) en ne gardant que les deux dernières valeurs, mais cette optimisation sort du programme.
| **Lisibilité** | Très lisible | Lisible | Moins intuitif |
| **Risque** | RecursionError pour n grand | RecursionError pour n grand | Aucun |
> En pratique, le **bottom-up** est souvent préféré en compétition et en entreprise car il évite les risques liés à la récursion. Le **top-down** est plus naturel quand on part d'une formule récursive.
---
### À retenir
- La **programmation dynamique** = décomposer + mémoriser + combiner
- Elle s'applique quand un problème a des **sous-problèmes qui se répètent**
- Deux approches : **top-down** (mémoïsation, récursif) et **bottom-up** (tableau, itératif)
- Les deux ont une complexité **polynomiale** là où la version naïve est souvent **exponentielle**
---
Auteur : Florian Mathieu
Licence CC BY NC
<arel="license"href="http://creativecommons.org/licenses/by-nc-sa/4.0/"><imgalt="Licence Creative Commons"style="border-width:0"src="https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png"/></a><br/>Ce cours est mis à disposition selon les termes de la <arel="license"href="http://creativecommons.org/licenses/by-nc-sa/4.0/">Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International</a>.
