Burst Balloons

Q: Quelle est la complexité temporelle de Burst Balloons ?

Temps O(n³) et mémoire O(n²) : environ n²/2 intervalles, chacun essayant jusqu’à n ballons en dernier. Pour 300 ballons, cela représente environ 4.5 × 10^6 étapes. Essayer tous les ordres prend O(n · n!) .

DifficileProgrammation dynamique

+10

Une rangée de ballons est représentée par nums, où nums[i] est le nombre inscrit sur le ballon i. Vous les faites tous éclater, un à la fois, dans n’importe quel ordre. Faire éclater un ballon rapporte left × nums[i] × right pièces, où left et right sont les nombres inscrits sur ses voisins actuels, c’est-à-dire les ballons les plus proches de chaque côté qui se trouvent encore dans la rangée. Un voisin manquant compte pour 1. Après qu’un ballon a éclaté, ses deux voisins deviennent adjacents. Retournez 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 plus grand nombre de pièces que vous pouvez collecter en faisant éclater tous les ballons

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: Fais éclater le 4 pour obtenir 2 × 4 × 3 = 24. Le 2, maintenant à côté du 3, rapporte 1 × 2 × 3 = 6, et le 3 rapporte 3 : 33 au total.

Pour aller plus loin

Peux-tu aussi 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 modifie les voisins, donc le premier ballon que tu éclates ne divise pas la rangée : les deux côtés deviennent voisins. C’est le dernier ballon éclaté d’un segment qui la divise. Il reste en place tandis que tout le reste disparaît, si bien que les segments de part et d’autre sont indépendants, et qu’une table d’intervalles sur les 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 un ballon, collecte left × value × right, retire-le, puis résous la rangée plus courte de la même façon, en gardant le meilleur total parmi tous les choix. Cette méthode essaie tous les ordres, elle est donc correcte.

Il y a n choix pour le premier ballon, puis n-1, et ainsi de suite : n! ordres, soit déjà 479,001,600 pour 12 ballons. Mémoriser les résultats pour chaque ensemble de ballons encore présents n’aide pas, car il existe 2^n ensembles.

Algorithme

Écrivez burstAll(row), le nombre maximal de pièces obtenues avec les ballons de row, 0 pour une rangée vide.
Pour chaque position k, gagnez left × row[k] × right, en utilisant 1 au-delà de chaque extrémité, plus burstAll de la rangée sans row[k].
Renvoyez le meilleur total parmi toutes les valeurs de k, et appelez 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 un mémo

Intuition

Complète la ligne avec un 1 à chaque extrémité : vals = [1] + nums + [1]. Les valeurs ajoutées n’éclatent jamais et remplacent les voisins manquants. Soit solve(left, right) le nombre maximal de pièces obtenues avec les ballons strictement situés entre deux positions encore occupées.

Supposons que k éclate en dernier dans cet intervalle. Tous les autres ballons qui s’y trouvent éclatent alors que k est encore là, comme un mur : la partie entre left et k ne voit que ses propres ballons et deux bordures fixes, et il en va de même pour la partie entre k et right. Lorsque k éclate, ses voisins sont exactement left et right. Le meilleur résultat pour l’intervalle est donc, pour chaque k, le meilleur des résultats des deux parties, auquel on ajoute vals[left] × vals[k] × vals[right]. La réponse correspond à l’intervalle entre les deux valeurs ajoutées. Il y a environ n²/2 intervalles, et chacun essaie jusqu’à n ballons : la mémoïsation ramène donc la complexité à O(n³).

Algorithme

Construis vals à partir de nums en ajoutant un 1 à 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 entre les deux comme dernier ballon, conserve la valeur maximale de solve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right], puis stocke-la.
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 des questions que sur des intervalles plus étroits. Remplis donc le même tableau avec des boucles, des intervalles étroits avant les larges. Ainsi, best[left][k] et best[k][right] sont définitifs lorsqu’un intervalle plus large en a besoin.

Pour [2, 4, 3], complété par [1, 2, 4, 3, 1], best[0][4] essaie de faire éclater chaque ballon en dernier. Si le 3 est le dernier, on obtient best[0][3] = 30 plus 1 × 3 × 1, soit 33, le meilleur des trois résultats.

Le travail est le même que dans la version avec mémoïsation, mais de simples boucles évitent des millions d’appels de fonction, ce qui rend cette version plusieurs fois plus rapide 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].
Renvoyez 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

Découper au premier ballon éclaté en utilisant ses voisins d’origine, nums[k-1] × nums[k] × nums[k+1], plus les deux côtés. Ces voisins ont peut-être déjà disparu : pour [2, 4, 3], le résultat est 44, soit davantage que ce que rapporte n’importe quel ordre réel.
Remplir le tableau ligne par ligne en faisant croître left. Alors best[k][right] pour k > left n’a pas encore été calculé et vaut 0. Remplis le tableau par largeur, ou parcours left en ordre décroissant.
Marquer une plage non résolue dans la mémoïsation avec 0. Une plage de ballons valant zéro rapporte réellement 0, donc elle est recalculée à chaque visite. Utilise -1.
En Lua et en R, les positions complétées vont de 1 à m, donc la réponse est best[1][m].

Questions fréquentes3

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

Après le premier éclatement, ses deux côtés deviennent voisins et continuent donc de s’influencer. Le dernier ballon d’un segment reste en place pendant que les autres éclatent, donc ses deux côtés ne se rencontrent jamais et chacun constitue un sous-problème indépendant. Lorsqu’il éclate, ses voisins sont les limites du segment.

Quelle est la complexité temporelle de Burst Balloons ?

Temps O(n³) et mémoire O(n²) : environ n²/2 intervalles, chacun essayant jusqu’à n ballons en dernier. Pour 300 ballons, cela représente environ 4.5 × 10^6 étapes. Essayer tous les ordres prend O(n · n!).

Peut-on résoudre le problème des ballons à éclater en choisissant un ordre glouton ?

Non. Faire éclater le plus petit ballon en premier rapporte 24 avec [2, 4, 3], alors qu’on peut obtenir 33. Faire éclater celui qui rapporte le plus à l’instant rapporte 42 avec [2, 9, 2], alors qu’en faisant éclater un 2 en premier, on obtient 18 + 18 + 9 = 45. Chaque ballon éclaté modifie le prix des suivants.

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

Test #1

Test #2

Test #3

Argument

nums = [2, 4, 3]

Résultat attendu

Burst Balloons

Fonction

Contraintes

Exemples

Indices

Solution

Essayez tous les ordres d’éclatement

Récursion sur le dernier ballon, avec un mémo

Remplissez le tableau des intervalles par largeur

Pièges et cas limites

Questions fréquentes3

Problèmes similaires