Questions d'entretien Dynamic programming
La programmation dynamique (DP) est un paradigme algorithmique fondamental testé dans les entretiens de codage des grandes entreprises technologiques. Elle évalue votre capacité à décomposer des problèmes complexes en sous-problèmes qui se chevauchent et à utiliser la mémorisation ou la tabulation. Les questions de DP impliquent souvent l'optimisation, les séquences et les problèmes combinatoires. Elles sont fréquemment posées pour les postes chez FAANG et d'autres entreprises de premier plan.
Ce que couvrent les entretiens Dynamic programming
Mémorisation vs tabulation
Comprenez les approches descendante (récursion + mémorisation) et ascendante (tabulation), leurs compromis et quand utiliser chacune.
Motifs DP courants
Maîtrisez les motifs classiques comme Fibonacci, Knapsack, la plus longue sous-séquence commune et la multiplication de chaînes de matrices pour reconnaître rapidement les problèmes DP.
Définition des états et transitions
Apprenez à définir l'état DP (par exemple, dp[i][j]) et à formuler des relations de récurrence qui expriment correctement les contraintes du problème.
Techniques d'optimisation
Utilisez l'optimisation de l'espace (par exemple, les tableaux roulants), les files monotones et d'autres techniques pour réduire la mémoire et le temps d'exécution des solutions DP.
Exemples de questions d'entretien Dynamic programming
- Expliquez la différence entre la mémorisation et la tabulation en DP.Ce qu'une bonne réponse couvre
- Approche descendante vs ascendante
- Récursivité + cache vs itération + tableau
- Complexité spatiale et temporelle
- Ordre de résolution des sous-problèmes
Voir un exemple de réponse
La mémorisation est une technique descendante (top-down) qui utilise la récursivité et un cache (souvent un dictionnaire ou un tableau) pour stocker les résultats des sous-problèmes déjà résolus. La tabulation est une approche ascendante (bottom-up) qui remplit itérativement un tableau en résolvant d'abord les sous-problèmes les plus petits. La mémorisation peut résoudre uniquement les sous-problèmes nécessaires, ce qui la rend plus efficace pour des espaces de recherche clairsemés, mais souffre d'un overhead récursif. La tabulation résout tous les sous-problèmes dans un ordre prédéfini, a généralement une meilleure performance constante et évite la récursivité. En termes de complexité spatiale, la mémorisation peut utiliser plus de mémoire si l'espace des états est grand, tandis que la tabulation peut souvent optimiser l'espace en ne gardant que les lignes nécessaires. Le choix dépend du problème : si l'ordre de résolution est naturel (comme dans Fibonacci), la tabulation est simple ; si la structure des sous-problèmes est complexe, la mémorisation est plus intuitive.
- Implémentez les nombres de Fibonacci en utilisant la DP (descendante et ascendante).Ce qu'une bonne réponse couvre
- Implémentation descendante avec récursivité et mémorisation
- Implémentation ascendante avec itération et espace optimisé
- Complexité temporelle O(n) et spatiale O(1) pour l'ascendante
Voir un exemple de réponse
Voici deux implémentations pour les nombres de Fibonacci. La version descendante utilise un dictionnaire pour mémoriser les résultats intermédiaires, avec une complexité temporelle O(n) et spatiale O(n) due à la pile de récursivité et au cache. La version ascendante optimise l'espace en ne gardant que les deux derniers nombres, atteignant O(1) en espace et O(n) en temps.
Solution de référencepython def fib_memo(n, memo={}): if n in memo: return memo[n] if n <= 1: return n memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo) return memo[n] def fib_tab(n): if n <= 1: return n a, b = 0, 1 for _ in range(2, n+1): a, b = b, a + b return b # Complexité : O(n) temps, O(1) espace pour tabulation - Étant donné un ensemble d'articles avec des poids et des valeurs, résolvez le problème du sac à dos 0/1 pour une valeur maximale.Ce qu'une bonne réponse couvre
- Construction d'une table DP 2D
- Initialisation de la première ligne/colonne à zéro
- Équation de transition basée sur le poids de l'article
- Complexité O(n*W) en temps et espace
Voir un exemple de réponse
Le problème du sac à dos 0/1 peut être résolu par programmation dynamique avec une table DP où dp[i][w] représente la valeur maximale atteignable avec les i premiers articles et un poids maximum w. L'initialisation met la première ligne et colonne à zéro. L'équation de transition est : si le poids de l'article i est inférieur ou égal à w, on prend le max entre ne pas prendre l'article (dp[i-1][w]) et le prendre (dp[i-1][w - poids[i]] + valeur[i]). Sinon, on ne peut pas le prendre. On parcourt tous les articles et poids. La complexité est O(n*W) en temps et O(n*W) en espace, mais on peut optimiser l'espace en utilisant un tableau 1D.
Solution de référencepython def knapsack_01(poids, valeurs, capacite): n = len(poids) dp = [[0] * (capacite + 1) for _ in range(n + 1)] for i in range(1, n + 1): for w in range(1, capacite + 1): if poids[i-1] <= w: dp[i][w] = max(dp[i-1][w], dp[i-1][w - poids[i-1]] + valeurs[i-1]) else: dp[i][w] = dp[i-1][w] return dp[n][capacite] # Complexité : O(n*capacite) temps, O(n*capacite) espace - Trouvez la longueur de la plus longue sous-séquence strictement croissante dans un tableau.Ce qu'une bonne réponse couvre
- Tableau DP où dp[i] est la LIS se terminant à l'index i
- Transition : pour chaque j < i, si arr[j] < arr[i], dp[i] = max(dp[i], dp[j]+1)
- Initialisation de dp[i] à 1
- Complexité O(n^2) en temps, O(n) en espace
Voir un exemple de réponse
Pour trouver la longueur de la plus longue sous-séquence strictement croissante (LIS), on utilise un tableau DP où dp[i] est la longueur de la LIS se terminant à l'index i. On initialise dp[i] à 1 pour chaque élément. Ensuite, pour chaque i, on regarde tous les j < i ; si arr[j] < arr[i], on met à jour dp[i] = max(dp[i], dp[j] + 1). La réponse est le maximum de tous les dp[i]. Cette approche a une complexité O(n^2) en temps et O(n) en espace. Il existe une optimisation en O(n log n) utilisant un tableau de piles, mais celle-ci est plus complexe.
Solution de référencepython def lis_longueur(arr): n = len(arr) dp = [1] * n for i in range(n): for j in range(i): if arr[j] < arr[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp) # Complexité : O(n^2) temps, O(n) espace - Calculez la distance d'édition (distance de Levenshtein) entre deux chaînes.Ce qu'une bonne réponse couvre
- Tableau DP 2D avec distance entre préfixes
- Initialisation de la première ligne et colonne avec les indices
- Trois opérations : insertion, suppression, substitution
- Coût unitaire pour chaque opération
- Complexité O(m*n) en temps et espace
Voir un exemple de réponse
La distance d'édition (Levenshtein) entre deux chaînes se calcule via une table DP où dp[i][j] est la distance entre les i premiers caractères de la première chaîne et les j premiers de la seconde. On initialise la première ligne avec j (insertions) et la première colonne avec i (suppressions). Pour chaque cellule, si les caractères sont égaux, dp[i][j] = dp[i-1][j-1] ; sinon, on prend le minimum entre insertion (dp[i][j-1]+1), suppression (dp[i-1][j]+1), et substitution (dp[i-1][j-1]+1). Le résultat est dp[m][n]. Complexité O(m*n) en temps et espace, mais on peut optimiser l'espace en utilisant deux lignes.
Solution de référencepython def distance_edition(s1, s2): m, n = len(s1), len(s2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m + 1): dp[i][0] = i for j in range(n + 1): dp[0][j] = j for i in range(1, m + 1): for j in range(1, n + 1): if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = min(dp[i-1][j] + 1, # suppression dp[i][j-1] + 1, # insertion dp[i-1][j-1] + 1) # substitution return dp[m][n] # Complexité : O(m*n) temps, O(m*n) espace - Résolvez le problème de rendu de monnaie : nombre minimum de pièces pour atteindre un montant donné.Ce qu'une bonne réponse couvre
- Tableau DP 1D de taille montant+1 initialisé à l'infini
- Initialisation de dp[0] = 0
- Pour chaque pièce, mise à jour de dp[montant] = min(dp[montant], dp[montant - pièce] + 1)
- Ordre des pièces : peut être itéré à l'extérieur ou à l'intérieur
- Complexité O(n*montant) avec n le nombre de pièces
Voir un exemple de réponse
Le problème du rendu de monnaie pour le nombre minimum de pièces se résout avec un tableau DP de taille montant+1, initialisé à une grande valeur (infini), sauf dp[0]=0. On parcourt chaque pièce, et pour chaque montant de la pièce à la valeur cible, on met à jour dp[montant] = min(dp[montant], dp[montant - pièce] + 1). Cette approche fonctionne car on considère chaque pièce de manière non limitée (supply infini). La complexité est O(n*montant) en temps et O(montant) en espace. Il faut faire attention à l'ordre des boucles : mettre les pièces en boucle externe permet d'éviter les permutations redondantes et garantit un nombre infini de chaque pièce.
Solution de référencepython def rendu_monnaie_min(pieces, montant): INF = float('inf') dp = [INF] * (montant + 1) dp[0] = 0 for p in pieces: for m in range(p, montant + 1): if dp[m - p] != INF: dp[m] = min(dp[m], dp[m - p] + 1) return dp[montant] if dp[montant] != INF else -1 # Complexité : O(len(pieces)*montant) temps, O(montant) espace - Comptez le nombre de façons de monter un escalier avec 1 ou 2 marches à la fois.Ce qu'une bonne réponse couvre
- Problème de comptage de chemins
- dp[i] = nombre de façons d'atteindre la marche i
- Base : dp[0]=1, dp[1]=1 (ou dp[1]=1, dp[2]=2 selon définition)
- Transition : dp[i] = dp[i-1] + dp[i-2]
- Optimisation d'espace possible
Voir un exemple de réponse
Pour compter le nombre de façons de monter un escalier de n marches en sautant 1 ou 2 marches à la fois, on utilise un tableau DP où dp[i] est le nombre de façons d'atteindre la marche i. On initialise dp[0]=1 (une façon de ne pas bouger) et dp[1]=1 (une seule marche). Ensuite, pour i de 2 à n, dp[i] = dp[i-1] + dp[i-2]. Le résultat est dp[n]. Cela forme une séquence de Fibonacci. On peut optimiser l'espace en ne gardant que les deux dernières valeurs. Complexité O(n) en temps et O(1) en espace.
Solution de référencepython def monter_escalier(n): if n <= 1: return 1 a, b = 1, 1 for _ in range(2, n + 1): a, b = b, a + b return b # Complexité : O(n) temps, O(1) espace - Décrivez l'approche étape par étape pour résoudre tout problème DP, de l'identification des sous-problèmes au codage de la solution.Ce qu'une bonne réponse couvre
- Identifier si le problème a une sous-structure optimale et des sous-problèmes qui se chevauchent
- Définir l'état DP et la signification de dp[...]
- Formuler la relation de récurrence
- Déterminer les cas de base et initialiser
- Choisir entre approche descendante (mémorisation) ou ascendante (tabulation)
- Appliquer l'ordre de résolution (parfois avec optimisation d'espace)
Voir un exemple de réponse
La résolution d'un problème de programmation dynamique suit généralement ces étapes. Premièrement, reconnaître que le problème peut être décomposé en sous-problèmes qui se chevauchent et possède une sous-structure optimale (la solution optimale du problème global dépend des solutions optimales de ses sous-problèmes). Deuxièmement, définir l'état DP : décider ce que représente chaque entrée du tableau DP (par exemple, dp[i] pour les i premiers éléments, dp[i][j] pour deux indices). Troisièmement, établir la relation de récurrence : comment passer d'un état plus petit à un état plus grand ? Quatrièmement, identifier les cas de base : les valeurs que l'on connaît sans calcul (souvent les premiers éléments). Cinquièmement, choisir l'implémentation : descendante avec récursion et mémorisation (plus intuitive) ou ascendante avec itération (plus efficace en pratique). Ensuite, coder en respectant l'ordre de résolution des sous-problèmes (pour l'approche ascendante, on remplit le tableau du plus petit au plus grand). Enfin, on peut souvent optimiser la mémoire en ne gardant que les lignes nécessaires (par exemple, deux lignes pour les problèmes 2D). Il est crucial de valider la récurrence avec des exemples simples et de tester les cas limites.
Comment se préparer
- Maîtrisez les motifs DP courants comme le sac à dos, la LCS et les problèmes de grille.
- Entraînez-vous à écrire des relations de récurrence à partir de zéro avant de coder.
- Commencez par une récursion de force brute, puis ajoutez la mémorisation, puis convertissez en tabulation si nécessaire.
- Utilisez des techniques d'optimisation de l'espace (par exemple, réduire la DP 2D à 1D) pour améliorer l'efficacité.
- Résolvez au moins 3 à 4 problèmes de chaque motif pour développer l'intuition de reconnaissance de la DP.
Questions fréquemment posées
Quelle est la différence clé entre la DP et la récursion ?
La DP stocke les résultats des sous-problèmes pour éviter les recalculs, tandis que la récursion sans mémorisation peut résoudre les mêmes sous-problèmes plusieurs fois.
Comment savoir si un problème peut être résolu avec la DP ?
Si le problème a des sous-problèmes qui se chevauchent et une sous-structure optimale (la solution optimale peut être construite à partir des solutions optimales des sous-problèmes), la DP est applicable.
Dois-je utiliser la mémorisation ou la tabulation lors des entretiens ?
La mémorisation est souvent plus facile à implémenter de manière descendante, mais la tabulation peut être plus économe en espace et éviter la profondeur de récursion. Choisissez en fonction de votre aisance et des contraintes du problème.
Quels sont les problèmes DP d'entretien les plus courants ?
Le sac à dos, la DP d'intervalle, l'alignement de séquences (LCS, distance d'édition), la multiplication de chaînes de matrices et la DP d'arbre sont fréquemment demandés.
Comment puis-je améliorer rapidement mes compétences en DP ?
Entraînez-vous à catégoriser les problèmes en motifs, résolvez 5 à 10 problèmes par motif et révisez les relations de récurrence pour développer l'intuition des transitions d'état.
Pratiquez les questions Dynamic programming avec des retours instantanés de l'IA
Téléchargez votre CV, obtenez un entretien simulé personnalisé et voyez exactement ce qu'il faut améliorer — gratuit pour commencer.