Programmation Dynamique
Calculer Fibonacci(50) prend une eternite en recursif naif... mais 50 microsecondes avec la programmation dynamique ! Le secret ? Ne JAMAIS recalculer deux fois la meme chose. On stocke les resultats intermediaires pour les reutiliser. C'est LA technique pour les problemes d'optimisation !
70 min Niveau 5/5 +60 XP
Objectifs
- Identifier les problemes avec sous-structure optimale
- Comprendre la memoisation (top-down)
- Implementer la tabulation (bottom-up)
- Resoudre les problemes classiques (Fibonacci, sac a dos)
Pieges a eviter
- !Confondre avec diviser pour regner (sous-problemes identiques)
- !Oublier d'initialiser le tableau de memoisation
- !Mauvaise definition de l'etat du sous-probleme
- !Ne pas identifier les chevauchements de sous-problemes
Cours complet
Contrairement a diviser pour regner, les sous-problemes se repetent. Fibonacci en est l'exemple parfait : fib(5) appelle fib(4) et fib(3), mais fib(4) rappelle aussi fib(3) !
# Fibonacci NAIF : explosion exponentielle !
def fib_naif(n):
"""O(2^n) - CATASTROPHIQUE !"""
if n <= 1:
return n
return fib_naif(n - 1) + fib_naif(n - 2)
# Arbre d'appels pour fib(5) :
# fib(5)
# / \
# fib(4) fib(3) <- fib(3) calcule 2 fois !
# / \ / \
# fib(3) fib(2) fib(2) fib(1) <- fib(2) calcule 3 fois !
# / \
# fib(2) fib(1)
# Nombre d'appels pour fib(n) :
# fib(10) : 177 appels
# fib(20) : 21,891 appels
# fib(30) : 2,692,537 appels
# fib(50) : 40 MILLIARDS d'appels !
import time
for n in [20, 25, 30]:
start = time.time()
resultat = fib_naif(n)
duree = time.time() - start
print(f"fib({n}) = {resultat}, temps = {duree:.3f}s")Quiz Prog. Dynamique
5 questions pour valider
Deux approches
Top-Down : Memoisation (recursif + cache)
Bottom-Up : Tabulation (iteratif + tableau)
A retenir
- • Sous-problemes chevauchants
- • Sous-structure optimale
- • Fibonacci : O(n) vs O(2^n)
