Qu'est-ce que la programmation dynamique en termes simples ?
Imaginez que vous comptez la factorielle du nombre 5.
Pour cela, vous devez calculer : 5 × 4 × 3 × 2 × 1. Et maintenant, on vous demande de calculer la factorielle de 6. Il est stupide de tout recompter, n'est-ce pas ? Vous savez déjà que 5! = 120, multipliez simplement par 6.
Programmation dynamique (PD) - c'est exactement la même approche : nous résolvons un problème complexe en le décomposant en sous-tâches, et mémoriser les résultatspour ne pas compter deux fois la même chose.
Les principales caractéristiques des tâches sur le PD :
🎯 Sous-structure optimale
La solution d'un gros problème consiste en des solutions de petits sous-problèmes
🔄 Sous-tâches qui se chevauchent
Les mêmes sous-tâches se rencontrent plusieurs fois
⚡ Il faut trouver l'optimum
Maximum, minimum ou nombre de méthodes
Deux approches de la PD : mémorisation et tabulation
1. Mémorisation (de haut en bas)
Il s'agit d'une récursion + mise en cache des résultats. Nous commençons par une grande tâche et nous descendons aux cas de base.
def fibonacci_memo(n, memo={}):
# Cas de base
if n <= 1:
return n
# Vérification du cache
if n in memo:
return memo[n]
# Calculer et enregistrer
memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
return memo[n]
print(fibonacci_memo(50)) # Immédiatement !Quand l'utiliser : lorsque la logique de la tâche est intuitivement compréhensible par récursion.
2. Tabulation (de bas en haut)
Nous construisons un tableau de solutions des cas de base à la réponse finale. Pas de récurrence !
def fibonacci_table(n):
if n <= 1:
return n
# Créons un tableau
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
# Remplissez de bas en haut
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print(fibonacci_table(50))Quand l'utiliser : lorsque vous avez besoin d'une performance maximale et d'un contrôle de la mémoire.
Problèmes classiques de PD à connaître en 2026
Tâche 1 : Les nombres de Fibonacci
Complexité sans DP : O(2ⁿ) — exponentiel !
Difficulté avec DP : O(n) est linéaire !
Nous avons déjà vu la solution ci-dessus. C'est une tâche idéale pour commencer.
Tâche 2 : Problème du sac à dos (Knapsack Problem)
Vous êtes un voleur avec un sac à dos d'une capacité de W. Il y a des objets avec un poids et une valeur. Comment prendre la valeur maximale ?
def knapsack(weights, values, capacity):
n = len(weights)
# dp[i][w] = valeur maximale pour i objets et capacité w
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(1, capacity + 1):
# Ne pas prendre l'objet
dp[i][w] = dp[i-1][w]
# Nous prenons l'objet s'il rentre
if weights[i-1] <= w:
dp[i][w] = max(
dp[i][w],
dp[i-1][w - weights[i-1]] + values[i-1]
)
return dp[n][capacity]
weights = [1, 2, 3, 5]
values = [10, 5, 15, 7]
capacity = 7
print(knapsack(weights, values, capacity)) # 32Application dans la réalité : allocation des ressources, planification budgétaire, optimisation de la charge du serveur.
Problème 3 : Longest Common Subsequence (LCS)
Trouver la plus longue sous-séquence commune de deux lignes. Base pour git diff !
def lcs(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
print(lcs("ABCDGH", "AEDFHR")) # 3 (ADH)Application : systèmes de contrôle de version, vérification du plagiat, bioinformatique (comparaison d'ADN).
Tâche 4 : Coin Change (Change de pièces)
Il y a des pièces de différentes valeurs. De combien de façons différentes peut-on collecter la somme ?
def coin_change(coins, amount):
# dp[i] = nombre minimum de pièces pour la somme i
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # Pour un montant de 0, il faut 0 pièces
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
coins = [1, 2, 5]
amount = 11print(coin_change(coins, amount)) # 3 (5+5+1)Application : applications fintech, systèmes de caisse, optimisation des transactions.
Tâche 5 : Edit Distance (Distance de Levenshtein)
Nombre minimum d'opérations pour transformer une ligne en une autre.
def edit_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Initialisation
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
# Remplissage du tableau
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(
dp[i-1][j], # suppression
dp[i][j-1], # insertion
dp[i-1][j-1] # remplacement
)
return dp[m][n]
print(edit_distance("kitten", "sitting")) # 3Application : correction des fautes de frappe, moteurs de recherche, saisie automatique.
Méthode pas à pas pour résoudre les problèmes de la PD
Étape 1 : Trouvez une solution récursive
Tout d'abord, résolvez simplement le problème par récursion sans penser à l'optimisation.
# Version non optimisée de fib(n) :
if n <= 1:
return n
return fib(n-1) + fib(n-2)Étape 2 : Ajoutez la mémoïsation
Ajoutez un dictionnaire pour stocker les résultats.
def fib_memo(n, memo={}):
if n <= 1:
return n
if n not in memo:
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]Étape 3 : Convertissez en tabulation (facultatif)
Passez à une approche itérative avec un tableau.
def fib_table(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]Étape 4 : Optimisez la mémoire
Souvent, vous pouvez utiliser O (1) mémoire au lieu de O (n).
def fib_optimized(n):
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
current = prev1 + prev2
prev2, prev1 = prev1, current
return prev1Principaux modèles de PD en 2026
1D DP
Tableau unidimensionnel
Nombres de Fibonacci
Climbing Stairs
House Robber
2D DP
Tableau à deux dimensions
Longest Common Subsequence
Edit Distance
Knapsack Problem
DP sur les lignes
Travail avec le texte
Palindrome Subsequences
String Matching
Wildcard Matching
DP sur les arbres
Structures arborescentes
Binary Tree Maximum Path Sum
Diameter of Binary Tree
DP sur les graphiques
Algorithmes de graphe
Shortest Path (Bellman-Ford)
Traveling Salesman Problem
Erreurs typiques des débutants
Erreur 1 : Oublier les cas de base
def fib(n):
return fib(n-1) + fib(n-2)
# Récursion infinie !Correct
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)Erreur 2 : Taille de tableau incorrecte
dp = [0] * n
# Si vous avez besoin d'index 0..n,
# besoin de la taille n+1 !Correct
dp = [0] * (n + 1)Erreur 3 : Ne pas vérifier les limites
if dp[i-1]:
# Et si i = 0 ?Correct
if i > 0 and dp[i-1]:Conseils pratiques pour les entretiens.
Dessinez un tableau sur papier — la visualisation aide à trouver des dépendances
Commencez par de petits exemples — fib(0), fib(1), fib(2)...
Cherchez la formule de récurrence — comment dp[i] dépend-il des valeurs précédentes ?
Énoncez la logique à voix haute - cela montre le cours de vos pensées
N'ayez pas peur d'écrire une solution non optimale au début - puis il peut être amélioré
Version JavaScript pour les développeurs web.
Beaucoup de débutants travaillent avec JavaScript, alors voici un exemple en JS :
// Mémorisationfunction fibMemo(n, memo = {}) {
if (n <= 1) return n;
if (memo[n]) return memo[n];
memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];
}
// Tabulationfunction fibTable(n) {
if (n <= 1) return n;
const dp = new Array(n + 1).fill(0);
dp[1] = 1;
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// Version optimisée (O(1) mémoire)function fibOptimized(n) {
if (n <= 1) return n;
let prev2 = 0, prev1 = 1;
for (let i = 2; i <= n; i++) {
const current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
console.log(fibOptimized(50)); // 12586269025Conclusion.
La programmation dynamique n'est pas de la magie, mais une approche logique de la résolution de problèmes. Points clés :
Divisez en sous-tâches — trouvez le motif de répétition
Conservez les résultats — ne comptez pas deux fois
Commencez par la récursion — puis optimisez
Entraînez-vous régulièrement — La PD nécessite de la pratique
Après avoir maîtrisé la programmation dynamique, vous :
✅ Passez la plupart des entretiens techniques
✅ Vous pourrez optimiser les tâches réelles en production
✅ Vous comprendrez le fonctionnement interne de nombreuses bibliothèques et frameworks
✅ Apprenez à penser de manière algorithmique
Rappelez-vous : chaque algorithme a déjà semblé complexe, même pour les meilleurs développeurs. L'essentiel est la pratique et la patience.
Vous pouvez étudier la programmation dynamique et de nombreux autres sujets importants dans Kodik — une plateforme éducative avec des cours pratiques pour les développeurs. Nous créons du contenu qui aide vraiment lors des entretiens et au travail !
📱 Et nous avons aussi un super Chaîne Telegram avec une communauté amicale où :
Analysons les tâches des entretiens
Nous partageons des articles utiles
Nous nous aidons mutuellement à grandir
Nous discutons des dernières tendances en matière de développement
Aller à Kodik Rejoindre Telegram
Rejoignez la communauté des développeurs qui grandissent ensemble ! 💪