# Programmation Dynamique
### Le programme
> 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.
---
### Motivation : un problème de performance
Dans le chapitre Récursivité, vous avez écrit la fonction `fibonacci` suivante :
```python
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
```
Et vous avez observé que l'arbre des appels contient de nombreux **doublons** :
```
fibonacci(5)
/ \
fibonacci(4) fibonacci(3) ← déjà calculé !
/ \ / \
fibonacci(3) fibonacci(2) fibonacci(2) fibonacci(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)
```
`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é)
fib(2) → calcule fib(1) = 1 ✓ et fib(0) = 0 ✓ → mémorise fib(2) = 1
fib(3) → fib(2) = 1 ✓ (déjà en memo) + fib(1) = 1 ✓ → mémorise fib(3) = 2
fib(4) → fib(3) = 2 ✓ (déjà en memo) + fib(2) = 1 ✓ → mémorise fib(4) = 3
fib(5) → fib(4) = 3 ✓ + fib(3) = 2 ✓ → mémorise fib(5) = 5
```
La complexité passe de O(2ⁿ) à **O(n)** en temps, et O(n) en mémoire (pour stocker le dictionnaire).
---
### Approche Bottom-Up : le tableau
On abandonne la récursion. On part des cas de base et on remplit un **tableau** dans l'ordre croissant jusqu'à atteindre la valeur souhaitée.
```python
def fibonacci_bottom_up(n):
if n == 0:
return 0
tableau = [0] * (n + 1) # tableau[i] contiendra fibonacci(i)
tableau[0] = 0
tableau[1] = 1
for i in range(2, n + 1):
tableau[i] = tableau[i-1] + tableau[i-2]
return tableau[n]
```
Déroulement pour `fibonacci_bottom_up(6)` :
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| tableau[i] | 0 | 1 | 1 | 2 | 3 | 5 | **8** |
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.
---
### Comparaison des trois approches
| Critère | Naïf (récursif) | Top-Down (mémoïsation) | Bottom-Up (tableau) |
|---------|-----------------|------------------------|----------------------|
| **Style** | Récursif | Récursif + dictionnaire | Itératif |
| **Complexité temps** | O(2ⁿ) | O(n) | O(n) |
| **Complexité espace** | O(n) pile d'appels | O(n) dictionnaire | O(n) tableau |
| **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
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.