Schéma de DP sur les intervalles et ordre de remplissage

La DP sur intervalles est un schéma de programmation dynamique dans lequel l'état dp[i][j] représente la réponse optimale pour le sous-problème couvrant les indices i à j. L'idée essentielle consiste à résoudre d'abord les intervalles plus petits, puis à construire la solution jusqu'à la plage complète. Ce schéma modélise naturellement des problèmes comme la multiplication en chaîne de matrices, le partitionnement en palindromes et l'éclatement de ballons, où les limites du sous-problème sont les extrémités gauche et droite d'une plage.

Pour la DP sur intervalles, l'état est dp[i][j] avec i <= j. Les cas de base sont les intervalles à un seul élément : dp[i][i]. Ils se résolvent trivialement — par exemple, une seule matrice a un coût de multiplication nul. Les intervalles à deux éléments dp[i][i+1] ont souvent eux aussi des réponses simples. Remplissez le tableau pour des longueurs d'intervalles croissantes, en commençant par la longueur 1 jusqu'à n.

Le détail essentiel de la DP sur intervalles est l'ordre de remplissage. Nous devons calculer tous les intervalles de longueur L avant de calculer ceux de longueur L+1, car un intervalle plus long dépend de sous-intervalles plus courts. La boucle externe parcourt la longueur de l'intervalle de 2 à n, la boucle intermédiaire définit la limite gauche i, et nous déduisons la limite droite avec j = i + L - 1.

Le problème classique de DP sur intervalles est la multiplication en chaîne de matrices : étant donné des matrices de dimensions dims[0..n], trouvez le nombre minimal de multiplications scalaires nécessaires pour calculer le produit. Multiplier la matrice A(p×q) par B(q×r) coûte p*q*r opérations. dp[i][j] = coût minimal pour multiplier les matrices i à j. Le point de coupure k détermine où la séquence est divisée en deux sous-chaînes.

Suivons l'exemple de multiplication en chaîne de matrices avec les dimensions [10, 30, 5, 60], qui représentent trois matrices : A(10×30), B(30×5), C(5×60). Pour dp[0][2], nous essayons une coupure à k=0 : dp[0][0] + dp[1][2] + 10×30×60 = 0 + 9000 + 18000 = 27000, puis à k=1 : dp[0][1] + dp[2][2] + 10×5×60 = 1500 + 0 + 3000 = 4500. Ainsi, dp[0][2] = 4500, en multipliant d'abord AB.

Lors du calcul de dp[i][j], nous faisons référence à dp[i][k] et dp[k+1][j] pour tout k dans [i, j-1]. Les deux sous-intervalles ont une longueur strictement inférieure à celle de [i, j]. En parcourant les longueurs de la plus petite à la plus grande, tous les sous-intervalles nécessaires sont calculés avant que nous en ayons besoin. Il s'agit de l'argument fondamental de correction de l'ordre de remplissage de la DP sur intervalles : les intervalles plus courts sont toujours des dépendances des plus longs.

La DP sur intervalles peut également être mise en œuvre de façon descendante avec mémoïsation. Nous écrivons une fonction récursive solve(i, j) qui renvoie le coût optimal pour l'intervalle [i, j], puis mémorisons les résultats dans un dictionnaire. L'ordre de remplissage est géré automatiquement par la récursion. L'approche descendante est souvent plus facile à comprendre, mais elle peut entraîner un surcoût dû aux appels de fonction ; l'approche ascendante est plus rapide en pratique pour les entrées volumineuses.

La DP sur intervalles possède O(n²) états (toutes les paires (i, j)) et chaque état parcourt O(n) points de coupure, ce qui donne au total une complexité de O(n³) time. L'espace utilisé est de O(n²) pour le tableau de DP. Pour une multiplication en chaîne de 100 matrices, cela représente 1 000 000 opérations — c'est tout à fait réalisable. Ce schéma apparaît dans de nombreux problèmes difficiles de LeetCode et est très apprécié lors des entretiens chez FAANG en raison de sa structure peu évidente.

Pour reconstruire le parenthésage réel (et pas seulement le coût), stockez un tableau séparé split[i][j] qui enregistre quel k a atteint le minimum pour chaque état. Lisez ensuite récursivement les coupures : reconstruct(i, j) affiche le regroupement optimal en effectuant une récursion sur [i, split[i][j]] et [split[i][j]+1, j]. Cette technique s'applique à tous les problèmes de DP sur intervalles.

Le modèle universel de DP sur intervalles comporte trois parties : (1) initialiser les cas de base pour les éléments seuls, (2) parcourir les longueurs croissantes et, pour chaque longueur, parcourir les limites gauches valides en calculant la limite droite, et (3) pour chaque intervalle, parcourir tous les points de coupure et appliquer la récurrence propre au problème. La seule chose qui change d'un problème à l'autre est la formule de récurrence à l'intérieur de la boucle la plus imbriquée.

Les problèmes qui utilisent la DP sur intervalles comprennent : Multiplication en chaîne de matrices (minimiser le nombre d'opérations), Éclatement de ballons (maximiser les pièces), Imprimante étrange (minimiser les opérations d'impression), Triangulation de polygone à score minimal et Partitionnement en palindromes II. Chacun utilise la même structure d'ordre de remplissage, mais des récurrences différentes. Reconnaissez le schéma lorsqu'un problème demande une valeur optimale sur une plage ou une séquence pouvant être divisée à n'importe quel point intérieur.

Testez votre compréhension des concepts de Structures de données & algorithmes — préparation aux entretiens de programmation de cette leçon.

Dans cette leçon, vous avez appris : la DP sur intervalles utilise dp[i][j] pour représenter la réponse optimale sur une plage, l'ordre de remplissage doit suivre des longueurs d'intervalles croissantes afin que les sous-intervalles soient calculés en premier, et le modèle universel utilise O(n³) time et O(n²) espace. Nous allons maintenant étudier la plus longue sous-séquence palindromique et la plus longue sous-chaîne palindromique avec ce même schéma.