Burst Balloons

+10

Une rangée de ballons est donnée sous la forme nums, où nums[i] est le nombre inscrit sur le ballon i. Vous les faites tous éclater, un à la fois, dans l’ordre de votre choix. Faire éclater un ballon rapporte left × nums[i] × right pièces, où left et right sont les nombres inscrits sur ses voisins actuels : les ballons les plus proches de chaque côté qui se trouvent encore dans la rangée. Un voisin manquant, au-delà de l’une ou l’autre extrémité de la rangée, compte pour 1. Après l’éclatement d’un ballon, ses deux voisins deviennent adjacents. Renvoyez le nombre maximal de pièces que vous pouvez collecter.

Fonction

maxCoins(nums: integer-array) → integer

numsinteger-array: les nombres sur les ballons, de gauche à droite
Renvoieinteger: le nombre maximal de pièces que vous pouvez collecter en faisant éclater chaque ballon

Contraintes

1 ≤ nums.length ≤ 300
0 ≤ nums[i] ≤ 100
La réponse est inférieure à 3 × 10⁸, donc elle tient dans un entier signé de 32 bits.

Exemples

Entrée: nums = [2, 4, 3]
Sortie: 33
Explication: Faites éclater le 4 en premier pour obtenir 2 × 4 × 3 = 24 pièces. Le 2 et le 3 sont maintenant voisins, donc faire éclater le 2 rapporte 1 × 2 × 3 = 6, et le 3, désormais seul, rapporte 1 × 3 × 1 = 3. Cela fait 33, et aucun autre ordre ne donne un meilleur résultat : faire éclater le petit 2 en premier vous limite déjà à 24.

+15 tests cachés à la soumission

Pour aller plus loin

Peux-tu également renvoyer un ordre d’éclatement qui rapporte le plus de pièces ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Chaque éclatement change les ballons voisins, donc un choix effectué maintenant modifie le coût de chaque éclatement ultérieur. Essayer tous les ordres revient à considérer n! séquences. Réfléchir au premier ballon à éclater ne divise pas non plus la rangée, car ses deux côtés deviennent voisins. En revanche, réfléchir au dernier ballon à éclater dans un segment fonctionne : il reste en place pendant que tous les autres éclatent, de sorte que le segment à sa gauche et celui à sa droite sont indépendants. Un tableau d’intervalles portant sur ces segments résout le problème en O(n³).

Essayez tous les ordres d’éclatement

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Choisis n’importe quel ballon à éclater maintenant, récupère left × value × right avec ses voisins actuels, retire-le de la rangée, puis résous la rangée raccourcie de la même manière. Fais cela pour chaque choix et garde le meilleur total. Une fonction récursive burstAll(row) fait exactement cela. Elle explore tous les ordres possibles, donc la réponse est correcte.

Cette méthode est impossible à utiliser avec des tailles réelles. Le premier ballon à éclater offre n choix, le deuxième n-1, et ainsi de suite : n! ordres. Pour 12 ballons, cela représente déjà 479,001,600 ordres, et le plus grand test comporte 120 ballons. Mémoriser les résultats pour chaque ensemble de ballons encore présents ne résout pas le problème, car il existe 2^n ensembles de ce type.

Pour trouver une solution, il faut comprendre pourquoi il y a autant de sous-problèmes. Après avoir éclaté le ballon k, le ballon à sa gauche et celui à sa droite se retrouvent côte à côte : ce qui se passe à gauche dépend donc toujours de la droite. L’approche suivante choisit le ballon sur lequel se concentrer de sorte que les deux côtés cessent de s’influencer.

Algorithme

Écris burstAll(row), qui renvoie le nombre maximal de pièces obtenues avec les ballons de row.
Pour chaque position k, lis les voisins, en utilisant 1 au-delà de chaque extrémité.
Gagne left × row[k] × right, puis ajoute le résultat de burstAll appliqué à la ligne sans row[k].
Renvoie le meilleur total pour toutes les valeurs de k, ou 0 si la ligne est vide.
Appelle burstAll(nums).

def maxCoins(nums):
    # Most coins you can still collect from the balloons in row
    def burst_all(row):
        top = 0
        for k in range(len(row)):
            left = row[k - 1] if k > 0 else 1
            right = row[k + 1] if k + 1 < len(row) else 1
            # Burst row[k] now, then do as well as possible with the rest
            coins = left * row[k] * right + burst_all(row[:k] + row[k + 1:])
            top = max(top, coins)
        return top

    return burst_all(nums)

Récursion sur le dernier ballon, avec une note

Intuition

D’abord, place un 1 aux deux extrémités : vals = [1] + nums + [1]. Ces deux ballons n’éclatent jamais et représentent les voisins manquants aux bords. Considère maintenant un intervalle entre deux positions left et right qui sont encore présentes, et demande-toi : quel ballon à l’intérieur de l’intervalle éclate en dernier ?

Disons que c’est k. Pendant que les autres ballons de l’intervalle éclatent, k est toujours là, debout entre eux comme un mur. Tous les ballons entre left et k n’ont pour voisins que ceux de cette portion, avec left et k comme limites fixes ; il en va de même entre k et right. Les deux portions sont donc des problèmes indépendants du même type. Lorsque k éclate enfin, tout ce qui se trouvait entre les limites a disparu : ses voisins sont donc exactement left et right, et il rapporte vals[left] × vals[k] × vals[right]. Choisir le premier ballon ne permet pas une telle division, car ses deux côtés deviennent voisins.

Cela donne une relation de récurrence. solve(left, right) renvoie le nombre maximal de pièces obtenu avec les ballons situés strictement entre left et right : 0 si l’intervalle est vide, sinon le plus grand résultat de solve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right] pour chaque k de l’intervalle. La réponse est solve(0, m-1), l’intervalle entre les deux bornes.

À elle seule, la récursion retombe encore et encore sur les mêmes intervalles. Stocke donc chaque résultat dans un tableau memo[left][right] et renvoie-le lors des visites suivantes. Il y a environ n²/2 intervalles, chacun essaie jusqu’à n ballons : le travail est donc de O(n³). Utilise -1 pour un intervalle pas encore résolu, car 0 est une réponse possible. La récursion ne descend jamais à plus de n+1 appels, puisque chaque appel travaille sur un intervalle plus étroit.

Algorithme

Construis vals comme nums avec un 1 ajouté à chaque extrémité, et définis m comme sa longueur.
Crée un mémo m × m rempli de -1.
Écris solve(left, right) : renvoie 0 si right - left < 2, et la valeur stockée s’il y en a une.
Sinon, essaie chaque k strictement compris entre les deux comme dernier ballon, conserve le résultat maximal de solve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right], puis stocke-le.
Renvoie solve(0, m-1).

def maxCoins(nums):
    # A 1 on each side stands for the ends of the row
    vals = [1] + nums + [1]
    m = len(vals)
    memo = [[-1] * m for _ in range(m)]

    # Most coins from the balloons strictly between left and right
    def solve(left, right):
        if right - left < 2:
            return 0
        if memo[left][right] >= 0:
            return memo[left][right]
        top = 0
        for last in range(left + 1, right):
            # last bursts after every other balloon in the gap
            coins = solve(left, last) + solve(last, right) + vals[left] * vals[last] * vals[right]
            top = max(top, coins)
        memo[left][right] = top
        return top

    return solve(0, m - 1)

Remplissez le tableau des intervalles par largeur

Intuition

La récursion ne pose de questions que sur des intervalles plus étroits. Tu peux donc remplir la même table sans récursion, à condition de remplir les intervalles étroits avant les larges. Soit best[left][right] le nombre maximal de pièces obtenues avec les ballons strictement compris entre left et right, soit 0 si l’intervalle est vide. Pour chaque largeur à partir de 2, et pour chaque intervalle de cette largeur, essaie chaque k à l’intérieur comme dernier ballon. best[left][k] et best[k][right] sont des intervalles plus étroits, donc leurs valeurs sont déjà définitives.

Prenons [2, 4, 3]. Avec les valeurs de bord ajoutées, on obtient vals = [1, 2, 4, 3, 1] aux positions 0 à 4, et la réponse est best[0][4]. Remplis les intervalles du plus étroit au plus large :

Largeur 2, un ballon à l’intérieur : best[0][2] = 1 × 2 × 4 = 8, best[1][3] = 2 × 4 × 3 = 24, best[2][4] = 4 × 3 × 1 = 12.
best[0][3], ballons 2 et 4 : si le 2 est le dernier, on obtient 0 + 24 + 1 × 2 × 3 = 30 ; si le 4 est le dernier, on obtient 8 + 0 + 1 × 4 × 3 = 20. Donc 30.
best[1][4], ballons 4 et 3 : si le 4 est le dernier, on obtient 0 + 12 + 2 × 4 × 1 = 20 ; si le 3 est le dernier, on obtient 24 + 0 + 2 × 3 × 1 = 30. Donc 30.
best[0][4], les trois ballons : si le 2 est le dernier, on obtient 0 + 30 + 1 × 2 × 1 = 32 ; si le 4 est le dernier, on obtient 8 + 12 + 1 × 4 × 1 = 24 ; si le 3 est le dernier, on obtient 30 + 0 + 1 × 3 × 1 = 33. Donc 33.

En remontant les choix gagnants, tu obtiens l’ordre suivant : le 3 éclate en dernier, avant lui le 2 est le dernier de la partie située à sa gauche, et le 4 éclate en premier. Cela donne 24 + 6 + 3 = 33.

Le travail est le même qu’avec la mémoïsation : 302 × 301 × 300 / 6 ≈ 4.5 × 10^6 étapes pour 300 ballons, et une table de 302 × 302 nombres. Les boucles simples évitent des millions d’appels de fonction, ce qui rend cette version plusieurs fois plus rapide que la récursion dans un langage comme Python ou R.

Algorithme

Construisez vals comme nums avec un 1 ajouté à chaque extrémité, et définissez m comme sa longueur.
Créez un tableau m × m best rempli de 0.
Pour chaque largeur de 2 à m-1, et chaque left tel que right = left + width se trouve dans le tableau, essayez chaque k strictement entre les deux.
Définissez best[left][right] comme le plus grand best[left][k] + best[k][right] + vals[left] × vals[k] × vals[right].
Retournez best[0][m-1].

def maxCoins(nums):
    # A 1 on each side stands for the ends of the row
    vals = [1] + nums + [1]
    m = len(vals)
    # best[left][right]: most coins from the balloons strictly between left and right
    best = [[0] * m for _ in range(m)]
    for width in range(2, m):
        for left in range(m - width):
            right = left + width
            edge = vals[left] * vals[right]
            top = 0
            for last in range(left + 1, right):
                # last goes after every other balloon in the gap,
                # so left and right are its neighbours when it bursts
                coins = best[left][last] + best[last][right] + edge * vals[last]
                if coins > top:
                    top = coins
            best[left][right] = top
    return best[0][m - 1]

Pièges et cas limites

Les erreurs habituelles sont un ordre glouton, une récursion sur le premier ballon éclaté, un mauvais marqueur de mémoïsation et un tableau rempli dans le mauvais ordre.

Les ordres gloutons échouent. Éclater le plus petit ballon en premier rapporte 24 sur [2, 4, 3] au lieu de 33, et éclater le ballon qui rapporte le plus à l’instant présent rapporte 42 sur [2, 9, 2], tandis qu’éclater un 2 en premier rapporte 18 + 18 + 9 = 45.
Découper selon le premier ballon éclaté en utilisant ses voisins d’origine, nums[k-1] × nums[k] × nums[k+1], puis ajouter les deux côtés, revient à compter des voisins qui ont peut-être déjà disparu. Sur [2, 4, 3], cela donne 44, davantage que ce que rapporte n’importe quel ordre réel.
Compter les bords comme faisant partie de l’intervalle. left et right sont toujours debout quand l’intervalle est vidé ; seuls les ballons situés strictement entre eux éclatent.
Remplir le tableau ligne par ligne en faisant augmenter left. Alors best[k][right] pour k > left n’est pas encore calculé et vaut 0 à la lecture. Remplis le tableau par largeur, ou parcours left en ordre décroissant.
Marquer un intervalle non résolu dans la mémoïsation avec 0. Un intervalle rempli de ballons de valeur zéro vaut réellement 0 ; il semble donc toujours non résolu et est recalculé à chaque visite. Utilise -1.
Oublier les deux 1 ajoutés aux extrémités, ce qui laisse les ballons aux bouts sans voisin à multiplier.
En Lua et en R, les positions complétées vont de 1 à m, donc la réponse est best[1][m].

Questions fréquentes4

Pourquoi Burst Balloons choisit-il le dernier ballon plutôt que le premier ?

Après la première explosion, les ballons situés de part et d’autre deviennent voisins : la partie gauche et la partie droite continuent donc à s’influencer et ne peuvent pas être résolues séparément. Le dernier ballon d’un segment reste en place pendant que les autres éclatent : les deux côtés ne se rejoignent donc jamais et, lorsqu’il éclate, ses voisins sont les frontières fixes du segment. Chaque segment constitue ainsi un sous-problème indépendant, ce dont la programmation dynamique a besoin.

Quelle est la complexité temporelle de Burst Balloons ?

La table des intervalles comporte environ n²/2 espaces, et chacun essaie jusqu’à n ballons comme dernier, donc le temps est O(n³) et la mémoire O(n²). Pour 300 ballons, cela représente environ 4.5 × 10^6 étapes. Essayer tous les ordres est en O(n · n!).

Peut-on résoudre Burst Balloons avec un ordre glouton ?

Non. Chaque règle simple échoue sur une petite rangée. Faire éclater le plus petit ballon en premier rapporte 24 avec [2, 4, 3], alors qu’il est possible d’obtenir 33. Faire éclater le ballon qui rapporte le plus à l’instant présent rapporte 42 avec [2, 9, 2], alors qu’en faisant éclater un 2 en premier, on obtient 45. Faire éclater un ballon modifie les prix des suivants, il faut donc utiliser la programmation dynamique sur les intervalles.

Pourquoi ajouter un 1 aux deux extrémités du tableau ?

Un voisin manquant compte comme 1 ; ainsi, deux ballons de remplissage de valeur 1 qui n’éclatent jamais donnent à chaque vrai ballon deux voisins sans cas particuliers. Ils servent également de limites à l’ensemble du problème : la réponse est l’écart entre les deux ballons de remplissage, best[0][m-1].

Python

def maxCoins(nums):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

nums = [2, 4, 3]

Attendu

Burst Balloons

Fonction

Contraintes

Exemples

Indices

Solution

Essayez tous les ordres d’éclatement

Récursion sur le dernier ballon, avec une note

Remplissez le tableau des intervalles par largeur

Pièges et cas limites

Questions fréquentes4

Problèmes similaires