la programmation dynamique, tout comme la méthode diviser-pour-régner, résout des problèmes en combinant des solutions de sous-problèmes. Dans ce contexte, "programmation" fait référence à une méthode tabulaire plutôt qu'à la rédaction de code informatique. 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.

Cependant, la programmation dynamique diffère en ce qu'elle peut s'appliquer même lorsque les sous-problèmes ne sont pas indépendants. Autrement dit, des sous-problèmes peuvent partager des sous-sous-problèmes. Dans cette situation, un algorithme diviser-pour-régner effectue un travail redondant en résolvant plusieurs fois le même sous-sous-problème. En revanche, un algorithme de programmation dynamique résout chaque sous-sous-problème une seule fois et mémorise sa réponse dans un tableau. Cela évite ainsi de recalculer la solution à chaque rencontre du même sous-sous-problème.

La programmation dynamique est généralement utilisée pour résoudre des problèmes d'optimisation, où de nombreuses solutions possibles existent. Chaque solution a une valeur, et l'objectif est de trouver une solution ayant la valeur optimale, qu'elle soit minimale ou maximale. Il est important de noter qu'une solution optimale n'est pas nécessairement la solution optimale unique, car plusieurs solutions peuvent donner la même valeur optimale.

La relation de dépendance entre les sous-problèmes :

Suivant l'intensité de la dépendance entre les sous-problèmes des différents niveaux du DAG-multi-niveaux, on peut distinguer deux classes de problèmes de programmation dynamique :

1. La classe serial :

   Elle est constituée des problèmes de programmation dynamique pour lesquels la solution d'un sous-problème à un niveau N donné dépend uniquement des solutions des sous-problèmes du niveau N-1 dans le DAG. Par exemple, l'équation suivante (Équation 4.1) décrit le problème PCC du calcul du plus court chemin (all-to-all) dans un graphe orienté pondéré suivant l'algorithme de Floyd:

   \[ pk_{i,j} = \begin{cases} C_{i,j} & \text{si } k = 0 \\ \min(pk_{-1 i,j}, pk_{-1 i,k} + pk_{-1 k,j}) & \text{si } 1 \leq k \leq n-1 \end{cases} \]

2. La classe non-serial :

   Elle est constituée des problèmes de programmation dynamique pour lesquels la solution d'un sous-problème à un niveau N donné dépend des solutions des sous-problèmes de plusieurs niveaux précédents (inférieurs à N). Par exemple, le problème LCS (Longest Common Subsequence) de recherche de la plus longue sous-séquence commune de deux chaînes données, appartient à la classe non-serial. L'équation fonctionnelle suivante (Équation 4.2) illustre comment la solution optimale d'un sous-problème (i,j) dépend de plusieurs sous-problèmes des niveaux précédents:

   \[ L(i,j) = \begin{cases} 0 & \text{si } i = 0 \text{ ou } j = 0 \\ L(i-1,j-1) + 1 & \text{si } i,j \geq 1 \text{ et } x_i = y_j \\ \max\{L(i,j-1), L(i-1,j)\} & \text{si } i,j \geq 1 \text{ et } x_i \neq y_j \end{cases} \]

Le nombre de termes récursifs :

Suivant le nombre de termes récursifs (sous-problèmes) dans la (les) fonction(s) de composition de l'équation fonctionnelle décrivant le problème, on distingue deux classes de problèmes de programmation dynamique :

1. La classe monadique :

   Les problèmes de cette classe ont un seul terme récursif dans l'équation fonctionnelle. Par exemple, le problème LCS appartient à la classe monadique, car son équation fonctionnelle ne contient qu'un seul terme récursif à la fois.

2. La classe polyadique :

   Pour les problèmes de programmation dynamique avec plus d'un terme récursif dans l'équation fonctionnelle, comme le problème PCC décrit. Ce problème appartient à la classe polyadique car il fait intervenir deux termes récursifs.

Suivant le type de dépendance entre les sous-problèmes dans le DAG-multi-niveaux, la classification de Li et Wah permet d'avoir une idée générale sur la complexité de parallélisation des problèmes de programmation dynamique : les algorithmes parallèles pour les problèmes de la classe polyadique non-serial sont plus difficiles à concevoir.