Burst Balloons

+10

Dany jest rząd balonów zapisany jako nums, gdzie nums[i] oznacza liczbę na balonie i. Przebijasz wszystkie balony, po jednym naraz, w wybranej przez siebie kolejności. Za przebicie balonu otrzymujesz left × nums[i] × right monet, gdzie left i right to liczby na jego aktualnych sąsiadach: najbliższych balonach po obu stronach, które nadal znajdują się w rzędzie. Brakujący sąsiad, znajdujący się poza jednym z końców rzędu, jest liczony jako 1. Po przebiciu balonu jego dwaj sąsiedzi stają się sąsiadami. Zwróć maksymalną liczbę monet, jaką możesz zebrać.

Funkcja

maxCoins(nums: integer-array) → integer

numsinteger-array: liczby na balonach, od lewej do prawej
Zwracainteger: najwięcej monet, jakie możesz zebrać, przebijając każdy balon

Ograniczenia

1 ≤ nums.length ≤ 300
0 ≤ nums[i] ≤ 100
Odpowiedź jest mniejsza niż 3 × 10⁸, więc mieści się w 32-bitowej liczbie całkowitej ze znakiem.

Przykłady

Wejście: nums = [2, 4, 3]
Wyjście: 33
Wyjaśnienie: Zbij pierwsze 4, aby zdobyć 2 × 4 × 3 = 24 monet. 2 i 3 są teraz sąsiadami, więc zbicie 2 daje 1 × 2 × 3 = 6, a 3, teraz samotna, daje 1 × 3 × 1 = 3. To daje 33, a żadna inna kolejność nie przynosi lepszego wyniku: zbicie najpierw małej 2 ogranicza wynik do 24.

+15 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy możesz też zwrócić jedno zamówienie z fajerwerkami, które zapewnia najwięcej monet?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Każdy wybuch zmienia to, które balony znajdują się obok siebie, więc wybór dokonany teraz zmienia koszt każdego późniejszego wybuchu. Wypróbowanie wszystkich kolejności oznacza n! sekwencji. Myślenie o pierwszym balonie, który pęknie, również nie dzieli rzędu, ponieważ jego dwie strony stają się sąsiadami. Myślenie o ostatnim balonie, który pęknie w danym przedziale, już tak: pozostaje on na miejscu, podczas gdy wszystkie pozostałe znikają, więc przedział po jego lewej stronie i przedział po jego prawej stronie są niezależne. Tabela przedziałów dla tych przedziałów rozwiązuje problem w O(n³).

Wypróbuj każdą kolejność wybuchania

Poprawne, ale nie kończy się na największych testach

Intuicja

Wybierz dowolny balon, który chcesz teraz przebić, zbierz left × value × right z jego aktualnymi sąsiadami, usuń go z rzędu i rozwiąż krótszy rząd w ten sam sposób. Zrób to dla każdego wyboru i zachowaj najlepszy łączny wynik. Funkcja rekurencyjna burstAll(row) robi dokładnie to. Sprawdza każdą możliwą kolejność, więc wynik jest poprawny.

To beznadziejne rozwiązanie dla rzeczywistych rozmiarów. Pierwszy balon można wybrać na n sposobów, drugi na n-1 i tak dalej: n! kolejności. Dla 12 balonów daje to już 479,001,600 kolejności, a największy test obejmuje 120 balonów. Zapamiętywanie wyników dla każdego zestawu balonów, które nadal stoją, nie pomaga, ponieważ takich zestawów jest 2^n.

Wyjściem jest zauważenie, dlaczego jest tak wiele podproblemów. Po przebiciu balonu k balon po jego lewej stronie i balon po jego prawej stronie stykają się, więc to, co dzieje się po lewej, nadal zależy od prawej strony. Kolejne podejście wybiera balon, o którym należy pomyśleć, tak aby obie strony przestały na siebie wpływać.

Algorytm

Napisz burstAll(row), która zwraca największą liczbę monet z balonów w row.
Dla każdej pozycji k odczytaj sąsiadów, używając 1 poza każdym z końców.
Zdobądź left × row[k] × right i dodaj wynik burstAll dla wiersza bez row[k].
Zwróć najlepszy łączny wynik dla wszystkich k albo 0 dla pustego wiersza.
Wywołaj 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)

Rekurencja na ostatnim balonie z memoizacją

Intuicja

Najpierw umieść 1 na obu końcach: vals = [1] + nums + [1]. Te dwie nigdy nie pękają i zastępują brakujących sąsiadów na krawędziach. Teraz przyjrzyj się przerwie między dwiema pozycjami left i right, które nadal stoją, i zadaj sobie pytanie: który balon w tej przerwie pęknie ostatni?

Załóżmy, że jest to k. Gdy pozostałe balony w przerwie pękają, k nadal tam jest, stojąc między nimi jak ściana. Każdy balon między left a k ma sąsiadów tylko z tego fragmentu, z left i k jako stałymi granicami; to samo dotyczy fragmentu między k a right. Te dwa fragmenty są więc niezależnymi problemami tego samego rodzaju. Gdy k w końcu pęknie, wszystko między granicami już zniknie, więc jego sąsiadami będą dokładnie left i right, a on przyniesie vals[left] × vals[k] × vals[right] monet. Wybór pierwszego balonu nie daje takiego podziału, ponieważ jego dwie strony stają się sąsiadami.

To prowadzi do rekurencji. solve(left, right) zwraca największą liczbę monet, jaką można zdobyć z balonów znajdujących się ściśle między left a right: 0, gdy przerwa jest pusta, a w przeciwnym razie największą wartość solve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right] dla każdego k w tej przerwie. Odpowiedzią jest solve(0, m-1), czyli przerwa między dwiema podstawkami.

Sama rekurencja wielokrotnie napotyka te same przerwy, więc zapisuj każdy wynik w tabeli memo[left][right] i zwracaj go przy kolejnej wizycie. Jest około n²/2 przerw, a dla każdej z nich sprawdzanych jest do n balonów, więc złożoność obliczeniowa wynosi O(n³). Użyj -1 dla przerwy, która nie została jeszcze rozwiązana, ponieważ 0 jest prawidłowym wynikiem. Rekurencja nigdy nie zagłębia się bardziej niż na n+1 wywołań, ponieważ każde wywołanie działa na węższej przerwie.

Algorytm

Zbuduj vals na podstawie nums, dodając 1 na obu końcach, i ustaw m na długość tej tablicy.
Utwórz tablicę m × m wypełnioną wartościami -1.
Napisz solve(left, right): zwróć 0, jeśli right - left < 2, a jeśli istnieje zapisana wartość — zwróć ją.
W przeciwnym razie wypróbuj każde k leżące ściśle między nimi jako ostatni balon, zachowaj największą wartość solve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right] i ją zapisz.
Zwróć 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)

Uzupełnij tabelę przedziałów według szerokości

Intuicja

Rekurencja zawsze pyta tylko o węższe przedziały. Możesz więc wypełnić tę samą tabelę bez rekurencji, o ile najpierw wypełnisz wąskie przedziały, a potem szerokie. Niech best[left][right] oznacza maksymalną liczbę monet z balonów znajdujących się ściśle między left i right; dla przedziału, w którym nic nie ma, wynosi 0. Dla każdej szerokości od 2 wzwyż i każdego przedziału o tej szerokości wypróbuj każde k wewnątrz jako ostatni balon. best[left][k] i best[k][right] dotyczą węższych przedziałów, więc ich wartości są już ostateczne.

Weźmy [2, 4, 3]. Po uzupełnieniu skrajów mamy vals = [1, 2, 4, 3, 1] na pozycjach od 0 do 4, a odpowiedzią jest best[0][4]. Wypełniaj przedziały, zaczynając od najwęższych:

Szerokość 2, jeden balon wewnątrz: best[0][2] = 1 × 2 × 4 = 8, best[1][3] = 2 × 4 × 3 = 24, best[2][4] = 4 × 3 × 1 = 12.
best[0][3], balony 2 i 4: jeśli ostatni będzie 2, otrzymamy 0 + 24 + 1 × 2 × 3 = 30; jeśli ostatni będzie 4, otrzymamy 8 + 0 + 1 × 4 × 3 = 20. Zatem 30.
best[1][4], balony 4 i 3: jeśli ostatni będzie 4, otrzymamy 0 + 12 + 2 × 4 × 1 = 20; jeśli ostatni będzie 3, otrzymamy 24 + 0 + 2 × 3 × 1 = 30. Zatem 30.
best[0][4], wszystkie trzy: jeśli ostatni będzie 2, otrzymamy 0 + 30 + 1 × 2 × 1 = 32; jeśli ostatni będzie 4, otrzymamy 8 + 12 + 1 × 4 × 1 = 24; jeśli ostatni będzie 3, otrzymamy 30 + 0 + 1 × 3 × 1 = 33. Zatem 33.

Odtwórz zwycięskie wybory i otrzymasz kolejność: 3 pęka jako ostatni, przed nim 2 jest ostatnim balonem w odcinku po jego lewej stronie, a 4 pęka jako pierwszy. To daje 24 + 6 + 3 = 33.

Obliczenia są takie same jak w przypadku memoizacji: 302 × 301 × 300 / 6 ≈ 4.5 × 10^6 kroków dla 300 balonów oraz tabela złożona z 302 × 302 liczb. Zwykłe pętle pozwalają uniknąć milionów wywołań funkcji, dzięki czemu ta wersja jest kilka razy szybsza niż rekurencja w języku takim jak Python lub R.

Algorytm

Zbuduj vals jako nums z dodaną jedynką na każdym końcu i ustaw m na jego długość.
Utwórz tabelę m × m best wypełnioną zerami.
Dla każdej szerokości od 2 do m-1 oraz każdego left, dla którego right = left + width mieści się w tablicy, sprawdź każde k leżące ściśle między nimi.
Ustaw best[left][right] na największą wartość spośród best[left][k] + best[k][right] + vals[left] × vals[k] × vals[right].
Zwróć 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]

Pułapki i przypadki brzegowe

Typowe błędy to zachłanne wybieranie kolejności, rekurencja oparta na pierwszym przebitym balonie, niewłaściwy znacznik w tablicy memoizacji oraz wypełnianie tabeli w złej kolejności.

Zachłanne wybieranie kolejności nie działa. Przebicie najpierw najmniejszego balonu daje 24 dla [2, 4, 3] zamiast 33, a przebicie balonu, który daje teraz najwięcej, daje 42 dla [2, 9, 2], podczas gdy przebicie najpierw balonu o wartości 2 daje 18 + 18 + 9 = 45.
Podział według pierwszego przebitego balonu z uwzględnieniem jego pierwotnych sąsiadów, nums[k-1] × nums[k] × nums[k+1], plus wyniki dla dwóch stron, uwzględnia sąsiadów, których może już nie być. Dla [2, 4, 3] daje wynik 44, większy niż wynik osiągalny przy dowolnej rzeczywistej kolejności.
Liczenie brzegów jako części odstępu. left i right nadal stoją, gdy odstęp zostaje opróżniony; przebijane są tylko balony znajdujące się ściśle między nimi.
Wypełnianie tabeli wiersz po wierszu, zwiększając left. Wtedy best[k][right] dla k > left nie zostało jeszcze obliczone i odczytywana jest wartość 0. Wypełniaj tabelę według szerokości albo zmniejszaj left.
Oznaczanie nierozwiązanego odstępu w tablicy memoizacji wartością 0. Odstęp zawierający same balony o wartości zero rzeczywiście ma wartość 0, więc wygląda na nierozwiązany na zawsze i jest rozwiązywany ponownie przy każdej wizycie. Użyj -1.
Zapominanie o dwóch uzupełniających jedynkach, przez co balony na końcach nie mają sąsiada, z którym można je pomnożyć.
W Lua i R pozycje uzupełniające mają indeksy od 1 do m, więc odpowiedzią jest best[1][m].

Najczęstsze pytania4

Dlaczego Burst Balloons wybiera ostatni balon zamiast pierwszego?

Po pierwszym przebiciu balony po jego obu stronach stają się sąsiadami, więc lewa i prawa część nadal na siebie wpływają i nie można rozwiązać ich osobno. Ostatni balon w przedziale pozostaje na miejscu, gdy pozostałe są przebijane, więc obie strony nigdy się nie stykają, a gdy zostanie przebity, jego sąsiadami będą stałe granice przedziału. Dzięki temu każdy przedział jest niezależnym podproblemem, czego wymaga programowanie dynamiczne.

Jaka jest złożoność czasowa problemu Burst Balloons?

Tablica przedziałów ma około n²/2 luk, a dla każdej z nich sprawdzamy do n balonów jako ostatni, więc złożoność czasowa wynosi O(n³), a pamięciowa O(n²). Dla 300 balonów daje to około 4.5 × 10^6 kroków. Sprawdzanie wszystkich kolejności ma złożoność O(n · n!).

Czy można rozwiązać problem pękających balonów, stosując zachłanną kolejność?

Nie. Każda prosta reguła zawodzi dla krótkiego rzędu. Przekłucie najpierw najmniejszego balonu daje 24 dla [2, 4, 3], choć można uzyskać 33. Przekłucie balonu, który daje teraz najwięcej, daje 42 dla [2, 9, 2], choć przekłucie najpierw balonu z wartością 2 daje 45. Przekłucie zmienia wartości późniejszych balonów, więc potrzebujesz programowania dynamicznego na przedziałach.

Dlaczego dodajemy 1 na obu końcach tablicy?

Brakujący sąsiad jest liczony jako 1, więc dwa balony wypełniające o wartości 1, które nigdy nie pękają, zapewniają każdemu prawdziwemu balonowi dwóch sąsiadów bez wyjątków. Służą też jako granice całego problemu: odpowiedzią jest różnica między dwoma balonami wypełniającymi, best[0][m-1].

Python

def maxCoins(nums):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

nums = [2, 4, 3]

Oczekiwane

Burst Balloons

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Wypróbuj każdą kolejność wybuchania

Rekurencja na ostatnim balonie z memoizacją

Uzupełnij tabelę przedziałów według szerokości

Pułapki i przypadki brzegowe

Najczęstsze pytania4

Podobne zadania