.: Dynamic Programming (DP)

Dynamic Programming (DP), c’est un concept clé en algorithmique, souvent utilisé pour résoudre des problèmes complexes qui peuvent être découpés en sous-problèmes plus simples.

1. Idée principale

Dynamic Programming consiste à éviter de recalculer plusieurs fois les mêmes sous-problèmes.
Autrement dit, si ton problème peut être divisé en plusieurs sous-problèmes qui se répètent, DP permet de mémoriser leurs résultats pour les réutiliser.

C’est un peu comme faire ses devoirs une seule fois et garder les réponses pour ne pas les refaire.

2. Quand utiliser DP ?

Il y a deux conditions importantes :

Optimal Substructure (sous-structure optimale) :
La solution globale peut être construite à partir des solutions optimales de ses sous-problèmes.
Exemple : pour trouver le plus court chemin dans un graphe, le chemin optimal de A à C passe par le chemin optimal de A à B et de B à C.
Overlapping Subproblems (sous-problèmes qui se répètent) :
Les mêmes sous-problèmes apparaissent plusieurs fois dans la résolution du problème.
Exemple : Fibonacci : pour calculer F(5), on calcule F(3) et F(4), mais F(3) est recalculé si on n’utilise pas DP.

3. Deux manières de faire DP

Top-down avec mémorisation (Memoization)
- On résout le problème de façon récursive, mais on stocke les résultats déjà calculés.
- Exemple : Fibonacci avec mémorisation.
Bottom-up avec tabulation
- On commence par résoudre les plus petits sous-problèmes, puis on construit progressivement la solution finale.
- Exemple : Fibonacci avec un tableau dp[n].

4. Exemple simple : Fibonacci

Sans DP (beaucoup de calculs redondants)


F(5) = F(4) + F(3)
F(4) = F(3) + F(2)

Ici F(3) est calculé deux fois !

Avec DP (mémorisation)


dp[0] = 0
dp[1] = 1
dp[2] = dp[1] + dp[0] = 1
dp[3] = dp[2] + dp[1] = 2
dp[4] = dp[3] + dp[2] = 3
dp[5] = dp[4] + dp[3] = 5

Maintenant, chaque valeur est calculée une seule fois.

En résumé :

Dynamic Programming = découper + mémoriser + reconstruire la solution optimale.

.

vendredi 13 février 2026