La programmation dynamique est une technique algorithmique fondamentale en informatique, utilisée pour résoudre efficacement des problèmes complexes en les décomposant en sous-problèmes plus simples. Elle est particulièrement utile lorsque ces sous-problèmes se répètent et que leurs solutions peuvent être réutilisées.

Qu’est-ce que la programmation dynamique ?

La programmation dynamique (Dynamic Programming – DP) consiste à résoudre un problème en le divisant en sous-problèmes plus petits, à stocker les résultats de ces sous-problèmes, puis à les réutiliser afin d’éviter des calculs redondants. Contrairement à une approche naïve récursive qui recalculerait plusieurs fois les mêmes valeurs, la programmation dynamique optimise le temps d’exécution en mémorisant les résultats intermédiaires.

Elle repose sur deux principes fondamentaux :

1. Sous-structure optimale : la solution optimale d’un problème dépend des solutions optimales de ses sous-problèmes.
2. Chevauchement des sous-problèmes : les mêmes sous-problèmes sont résolus plusieurs fois dans une approche récursive classique.

Quand utiliser la programmation dynamique ?

On utilise la programmation dynamique lorsqu’un problème présente :

• Une structure récursive naturelle.
• Des sous-problèmes identiques qui apparaissent plusieurs fois.
• La possibilité de stocker des résultats intermédiaires.
• Un objectif d’optimisation (minimiser un coût, maximiser un gain, compter des combinaisons, etc.).

Des exemples classiques incluent : le calcul du plus court chemin, le problème du sac à dos (Knapsack), les suites numériques (comme Fibonacci), ou encore les problèmes de planification.

Comment savoir si un problème nécessite la programmation dynamique ?

Voici quelques questions à se poser :

• Le problème peut-il être divisé en sous-problèmes similaires ?
• Les mêmes calculs sont-ils effectués plusieurs fois ?
• Existe-t-il une relation de récurrence claire ?
• Cherche-t-on une solution optimale ?

Si la réponse est oui à plusieurs de ces questions, la programmation dynamique est probablement adaptée.

Les différentes approches

Il existe principalement deux manières d’implémenter la programmation dynamique :

1. Top-down (mémoïsation)

On utilise une approche récursive classique, mais on stocke les résultats déjà calculés dans une structure (tableau ou dictionnaire). Avant de recalculer une valeur, on vérifie si elle existe déjà.

2. Bottom-up (tabulation)

On construit progressivement la solution en remplissant un tableau à partir des cas de base. Cette approche est souvent plus performante car elle évite la surcharge liée à la récursion.

Exemple détaillé : la programmation dynamique avec Fibonacci

Le problème

La suite de Fibonacci est définie comme suit :

• F(0) = 0
• F(1) = 1
• F(n) = F(n−1) + F(n−2), pour n ≥ 2

Les premiers termes sont :

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Le problème consiste à calculer F(n).

Approche récursive naïve

Une implémentation simple en récursif serait :

F(n):
   si n == 0 retourner 0
   si n == 1 retourner 1
   retourner F(n-1) + F(n-2)


Problème

Si on calcule F(6), voici ce qui se passe :

F(6)

→ F(5) + F(4)

→ (F(4) + F(3)) + (F(3) + F(2))

→ ...

On remarque que :

• F(4) est calculé plusieurs fois
• F(3) est calculé plusieurs fois
• F(2) est recalculé encore et encore

Il y a donc chevauchement de sous-problèmes.

La complexité devient exponentielle : O(2ⁿ) → très inefficace.

Pourquoi la programmation dynamique fonctionne ici ?

Le problème vérifie les deux conditions essentielles :

• Sous-structure optimale
  • Pour calculer F(n), il suffit de connaître F(n−1) et F(n−2).
  • La solution dépend de solutions optimales de sous-problèmes.
• Chevauchement des sous-problèmes
  • Les mêmes valeurs sont recalculées plusieurs fois.

Conclusion : Programmation dynamique adaptée à cette problématique.

Solution : Avec la méthode Top-Down (Mémoïsation)

Principe

On garde la récursion, mais on mémorise les résultats déjà calculés.

Avant de calculer F(n), on vérifie si on l’a déjà calculé.

Pseudo-code

memo = tableau vide

F(n):
   si n dans memo:
       retourner memo[n]

   si n == 0:
       retourner 0
   si n == 1:
       retourner 1

   memo[n] = F(n-1) + F(n-2)
   
   retourner memo[n]


Résultat

• Chaque valeur est calculée une seule fois.
• Complexité :
  • Temps : O(n)
  • Mémoire : O(n)
• On transforme une complexité exponentielle en complexité linéaire.

La programmation dynamique est donc un outil puissant pour optimiser des algorithmes.

La programmation dynamique n’est pas simplement une technique d’optimisation, c’est une manière de penser les problèmes en termes de sous-structures réutilisables.

Savoir reconnaître les situations où elle s’applique est une compétence essentielle pour tout étudiant en informatique souhaitant maîtriser la conception d’algorithmes efficaces.

‍