Fibonacci par Programmation Dynamique
Algorithmique classique
Enonce
Calculer le $n$-ième terme de la suite de Fibonacci par programmation dynamique ascendante (bottom-up), sans récursion.
Signature attendue
def fibo_dp(n: int) -> int:Exemples
fibo_dp(0)→0fibo_dp(10)→55fibo_dp(30)→832040
📖 Rappel de cours
On garde les termes déjà calculés au lieu de les recalculer : deux variables suffisent, ou un tableau si l'énoncé le demande.
⚠ Le piège : La version récursive naïve recalcule les mêmes termes un nombre exponentiel de fois. La mémorisation ramène le coût à O(n) : c'est tout l'objet de l'exercice.
← Exercices Python pour la prépa — CPGE scientifique et ECG
Exercices du meme theme
- Combinaisons de k parmi n
- Flocon de Koch (coordonnées)
- Somme des Sous-ensembles
- Sac à Dos 0/1
- Plus Longue Sous-séquence Commune (LCS)
- Distance d'Édition (Levenshtein)
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.