Numérique et sciences informatiques (spécialité) · Terminale · Algorithmique

Programmation dynamique

• La programmation dynamique découpe un problème en sous-problèmes, règle les plus petits en premier, puis monte vers les plus grands en gardant en mémoire chaque résultat .
• Elle est utile quand les mêmes sous-problèmes reviennent souvent : c'est justement le cas où diviser pour régner perd son efficacité .
• Démarche : définir les sous-problèmes, écrire la relation de récurrence, puis programmer en méthode descendante (mémoïsation) ou ascendante (tableau) .
• Un tableau ou un dictionnaire conserve chaque résultat : chaque sous-problème n'est calculé qu'une seule fois, ce qui ramène Fibonacci d'un coût exponentiel à un coût linéaire.