Ballons à éclater : DP sur intervalles inversée

Étant donnés n ballons de valeurs nums, faire éclater le ballon i rapporte nums[i-1] * nums[i] * nums[i+1] pièces (le produit de sa valeur et de celles de ses voisins actuels). Après son éclatement, ses voisins deviennent adjacents. Trouvez le nombre maximal de pièces que vous pouvez obtenir en faisant éclater tous les ballons. La simulation naïve est difficile, car l’éclatement modifie les voisins — la DP par intervalles inversée contourne élégamment cette difficulté.

Si nous essayons de définir dp[i][j] comme le nombre maximal de pièces obtenu en faisant éclater les ballons de l’intervalle [i, j] et que nous réfléchissons au premier ballon à éclater, nous rencontrons un problème : faire éclater le ballon k en premier signifie que nums[k-1] et nums[k+1] doivent être ses voisins actuels — mais ces ballons pourraient être éclatés plus tard, ce qui modifierait dynamiquement les voisins. L’état est difficile à définir proprement dans le sens direct.

L’astuce consiste à réfléchir au ballon qui sera le dernier à éclater dans l’intervalle [i, j]. Lorsque le ballon k est le dernier à éclater dans [i, j], tous les autres ballons de [i, j] ont déjà disparu. Les voisins du ballon k sont donc exactement nums[i-1] et nums[j+1] — les ballons frontières situés juste à l’extérieur de l’intervalle. Le calcul des pièces rapportées par le dernier éclatement devient ainsi déterministe : il ne dépend pas de l’ordre des éclatements précédents.

Ajoutez des ballons sentinelles : ajoutez 1 au début et à la fin de nums pour obtenir nums = [1] + nums + [1]. Définissez dp[i][j] comme le nombre maximal de pièces obtenu en faisant éclater tous les ballons strictement compris entre les indices i et j (bornes exclues), où nums[i] et nums[j] sont les ballons frontières qui subsistent. Récurrence : pour chaque ballon candidat k dans (i, j) comme dernier ballon à éclater : dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]).

Nous complétons le tableau avec des sentinelles, initialisons la table DP à zéro (intervalle vide = 0 pièce), puis la remplissons par longueur d’intervalle croissante. La réponse finale est dp[0][n+1] : elle représente le nombre maximal de pièces obtenu en faisant éclater tous les ballons d’origine, les sentinelles servant de frontières permanentes.

Pour [3, 1, 5, 8], complété par des sentinelles pour obtenir [1, 3, 1, 5, 8, 1] (indices 0 à 5). Nous cherchons dp[0][5]. Pour les intervalles de longueur 2 (un ballon à l’intérieur) : dp[0][2] = 1*3*1=3, dp[1][3]=3*1*5=15, dp[2][4]=1*5*8=40, dp[3][5]=5*8*1=40. En poursuivant la construction, l’optimum consiste à faire éclater 1 en dernier parmi {3,1,5,8}, après avoir fait éclater ses voisins, pour un total de 167 pièces.

Il y a O(n²) intervalles et, pour chaque intervalle, nous essayons O(n) points de séparation, ce qui donne une complexité temporelle en O(n³). L’espace utilisé est de O(n²) pour la table DP. Pour n = 500 ballons, cela représente 125 millions d’opérations, ce qui reste réalisable avec les contraintes d’un entretien. L’ajout de sentinelles simplifie la gestion des frontières : sans elles, il faudrait vérifier explicitement si i-1 et j+1 restent dans les limites du tableau.

La même solution peut s’écrire de haut en bas avec @lru_cache, ce qui peut être plus intuitif à élaborer pendant un entretien. Définissez solve(i, j) comme le nombre maximal de pièces dans l’intervalle ouvert (i, j). La fonction essaie toutes les valeurs de k comme dernier ballon à éclater et mémorise les résultats. Les deux approches ont exactement les mêmes complexités temporelle et spatiale.

Une erreur courante consiste à définir dp[i][j] comme le nombre de pièces obtenu lorsque le premier ballon de [i,j] est éclaté, plutôt que le dernier. Cette approche échoue, car le calcul des pièces du premier éclatement dépend des ballons voisins qui n’ont pas encore été éclatés — et l’état de ces voisins change au fur et à mesure de la progression de l’algorithme. Pensez toujours au dernier élément dans la DP par intervalles lorsque les frontières dépendent des éléments restants.

Les sentinelles de valeur 1 sont choisies parce qu’elles jouent le rôle d’éléments neutres pour la multiplication. Lorsqu’un ballon frontière est le dernier à éclater, sa valeur en pièces est boundary * last * boundary = 1 * last * 1 = last. Utiliser 0 donnerait 0 pièce, ce qui serait incorrect, tandis que d’autres valeurs fausseraient le calcul. L’astuce des sentinelles réunit proprement tous les cas de frontière sans traiter séparément les ballons situés tout à gauche et tout à droite.

Dans la DP par intervalles standard (chaînage de matrices), le point de séparation k indique où diviser le problème en deux sous-problèmes résolus indépendamment. Dans le problème des ballons à éclater, k est le dernier ballon à éclater dans l’intervalle, ce qui rend les deux sous-intervalles [i,k] et [k,j] indépendants, puisque k est encore présent comme frontière. Cette perspective inversée est l’idée ingénieuse qui permet de résoudre le problème des ballons à éclater avec une DP par intervalles.

Vérifiez votre compréhension des concepts de Structures de données et algorithmes — Préparation aux entretiens de programmation présentés dans cette leçon.

Dans cette leçon, vous avez appris : la simulation vers l’avant échoue, car l’éclatement des ballons modifie les voisins de manière imprévisible, l’idée inverse consiste à définir k comme le dernier ballon éclaté dans un intervalle, ce qui fait de nums[i] et nums[j] ses voisins, et la récurrence dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]) avec un remplissage par des sentinelles fournit une solution en O(n³). Ensuite, nous passons à la programmation dynamique du sac à dos, en commençant par le sac à dos classique 0/1 et son optimisation de l’espace mémoire.