En informatique, la programmation dynamique est une méthode algorithmique pour résoudre des problèmes d'optimisation. Le concept a été introduit au début des années 1950 par Richard Bellman. À l'époque, le terme « programmation » signifie planification et ordonnancement. La programmation dynamique consiste à résoudre un problème en le décomposant en sous-problèmes, puis à résoudre les sous-problèmes, des plus petits aux plus grands en stockant les résultats intermédiaires. Elle a d'emblée connu un grand succès, car de nombreuses fonctions économiques de l'industrie étaient de ce type, comme la conduite et l'optimisation de procédés chimiques, ou la gestion de stocks. vignette|149x149px|Le graphe de dépendance des sous-problèmes pour le calcul de F5, le 5ème terme de la suite de Fibonacci. Illustrons la programmation dynamique sur le calcul du nème terme de la suite de Fibonacci, parfois utilisé comme exemple introductif dans un cours sur la programmation dynamique. La suite de Fibonacci est définie par F0 = 0, F1 = 1 et Fn = Fn-1 + Fn-2. La programmation dynamique s'appuie sur le principe d'optimalité de Bellman : une solution optimale d'un problème s'obtient en combinant des solutions optimales à des sous-problèmes. Sur l'exemple de la suite de Fibonacci, la solution Fn s'obtient en additionnant Fn-1 et Fn-2. La méthode de programmation dynamique, comme la méthode diviser pour régner, résout des problèmes en combinant des solutions de sous-problèmes. Les algorithmes diviser-pour-régner partitionnent le problème en sous-problèmes indépendants qu’ils résolvent récursivement, puis combinent leurs solutions pour résoudre le problème initial. La méthode diviser-pour-régner est inefficace si on doit résoudre plusieurs fois le même sous-problème. Par exemple, l'algorithme suivant est inefficace : fonction fibonacci(n) si n = 0 ou n = 1 retourner n sinon retourner fibonacci(n-1) + fibonacci(n-2) Le graphe de dépendance montré sur la droite n'est pas un arbre : cela illustre que les sous-problèmes se chevauchent.