Burst Balloons
Dany jest rząd balonów nums, gdzie nums[i] oznacza liczbę na balonie i. Przebijasz wszystkie balony, po jednym naraz, w dowolnej 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 każdej stronie, które nadal znajdują się w rzędzie. Brakujący sąsiad jest liczony jako 1. Po przebiciu balonu jego dwaj sąsiedzi stają się sąsiadami. Zwróć maksymalną liczbę monet, jaką możesz zebrać.
Funkcja
- 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 ≤ 3000 ≤ nums[i] ≤ 100- Odpowiedź jest mniejsza niż 3 × 108, 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
- Zamień 4 na 2 × 4 × 3 = 24. Dwójka, teraz obok 3, daje 1 × 2 × 3 = 6, a trójka daje 3: razem 33.
- Wejście
- nums = [6, 1, 2, 5]
- Wyjście
- 108
- Wyjaśnienie
- Rozbij 1 (6 × 1 × 2 = 12), potem 2, teraz między 6 a 5 (6 × 2 × 5 = 60), następnie 5 za 30 i 6 za 6: razem 108.
- Wejście
- nums = [8]
- Wyjście
- 8
- Wyjaśnienie
- Jedyny balon nie ma sąsiadów, a każdy brakujący sąsiad liczy się jako 1, więc otrzymuje 1 × 8 × 1 = 8.
Pytanie dodatkowe
Czy możesz też zwrócić jedno zamówienie z wybuchem, które przynosi najwięcej monet?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Załóżmy, że decydujesz, który balon przebić jako pierwszy. Jego dwaj sąsiedzi stają się sąsiadami, więc balony po jego lewej i prawej stronie nadal na siebie wpływają. Czy możesz w ten sposób podzielić problem na dwa mniejsze?
Odwróć pytanie i wybierz balon, który pęknie ostatni w danym przedziale. Do tego czasu stoi nieruchomo jak ściana, więc balony po jego lewej i prawej stronie nigdy nie stają się sąsiadami. Kiedy w końcu pęknie, jego sąsiadami będą dwa balony ograniczające ten przedział.
Umieść 1 na obu końcach
nums. Niechbest[left][right]oznacza maksymalną liczbę monet zdobytą za balony znajdujące się ściśle między pozycjamileftiright. Wypróbuj każdy balonkmiędzy nimi jako ostatni: daje onbest[left][k] + best[k][right]plusvals[left] × vals[k] × vals[right]. Wypełniaj najpierw krótkie odstępy, a potem długie.
Rozwiązanie
Każde pęknięcie zmienia to, które balony sąsiadują ze sobą, więc pierwszy balon, który pęknie, nie dzieli rzędu: jego dwa sąsiednie balony stają się sąsiadami. Ostatni balon, który pęka w danym odcinku, już go dzieli. Pozostaje na swoim miejscu, gdy wszystkie pozostałe znikają, więc odcinki po jego obu stronach są niezależne, a tablica przedziałów dla odcinkó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 balon, zbierz left × value × right, usuń go i rozwiąż w ten sam sposób krótszy rząd, zachowując najlepszy łączny wynik spośród wszystkich wyborów. Ta metoda sprawdza każdą kolejność, więc jest poprawna.
Przy pierwszym przebiciu jest n możliwości, przy następnym n-1 i tak dalej: n! kolejności, czyli już 479,001,600 dla 12 balonów. Zapamiętywanie wyników dla każdego zestawu pozostałych balonów nie pomaga, ponieważ istnieje 2^n zestawów.
Algorytm
- Napisz
burstAll(row), która zwraca największą liczbę monet możliwą do zdobycia z balonów wrow, a dla pustego wiersza zwraca 0. - Dla każdej pozycji
kzdobądźleft × row[k] × right, używając 1 poza każdym z końców, a następnie dodaj wynikburstAlldla wiersza bezrow[k]. - Zwróć największą sumę spośród wszystkich
ki wywołajburstAll(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 w przypadku ostatniego balonu, z notatką
Intuicja
Uzupełnij wiersz jedynką na obu końcach: vals = [1] + nums + [1]. Jedynki nigdy nie pękają i zastępują brakujących sąsiadów. Niech solve(left, right) oznacza maksymalną liczbę monet z balonów znajdujących się ściśle między dwiema stojącymi pozycjami.
Załóżmy, że k pęka jako ostatni w tej przerwie. Wszystkie pozostałe balony w niej pękają, gdy k stoi jak ściana, więc część między left a k widzi tylko własne balony i dwie ustalone granice; tak samo jest z częścią między k a right. Gdy k pęka, jego sąsiadami są dokładnie left i right. Zatem najlepszy wynik dla tej przerwy to, dla każdego k, najlepszy wynik z obu części plus vals[left] × vals[k] × vals[right]. Odpowiedzią jest wynik dla przerwy między dwiema jedynkami. Jest około n²/2 przerw, a dla każdej sprawdzamy do n balonów, więc memoizacja daje złożoność O(n³).
Algorytm
- Zbuduj
valsjakonumsz dodaną jedynką na obu końcach i ustawmna jego długość. - Utwórz tablicę memo o wymiarach
m × m, wypełnioną wartościami -1. - Napisz
solve(left, right): zwróć 0, jeśliright - left < 2, a jeśli istnieje zapisana wartość, zwróć ją. - W przeciwnym razie wypróbuj każdą wartość
kleżącą ściśle między nimi jako ostatni balonik, zachowaj największą wartośćsolve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right]i zapisz ją. - 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)Wypełnij tabelę przedziałów według szerokości
Intuicja
Rekurencja pyta tylko o węższe przedziały, więc wypełnij tę samą tablicę za pomocą pętli, od wąskich przedziałów do szerokich. Dzięki temu best[left][k] i best[k][right] będą już obliczone, gdy będą potrzebne przy szerszym przedziale.
Dla [2, 4, 3], uzupełnionego do [1, 2, 4, 3, 1], best[0][4] sprawdza każdy balon jako ostatni. Jeśli ostatni jest balon 3, otrzymujemy best[0][3] = 30 plus 1 × 3 × 1, czyli 33 — najlepszy wynik z trzech możliwości.
Wykonywana praca jest taka sama jak w wersji z memoizacją, ale zwykłe pętle pozwalają uniknąć milionów wywołań funkcji, dzięki czemu ta wersja działa kilka razy szybciej w języku takim jak Python czy R.
Algorytm
- Zbuduj
valsjakonums, dodając 1 na każdym końcu, i ustawmna jego długość. - Utwórz tabelę
m × mbestwypełnioną zerami. - Dla każdej szerokości od 2 do
m-1oraz każdegoleft, dla któregoright = left + widthmieści się w tablicy, sprawdź każdekleżące ściśle pomiędzy nimi. - Ustaw
best[left][right]na największą wartość spośródbest[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
- Podział przy pierwszym przebiciu, z uwzględnieniem jego pierwotnych sąsiadów:
nums[k-1] × nums[k] × nums[k+1]plus wartości po obu stronach. Tych sąsiadów może już nie być: dla[2, 4, 3]wynik wynosi 44, czyli więcej, niż daje jakakolwiek rzeczywista kolejność. - Wypełnianie tabeli wiersz po wierszu, zwiększając
left. Wtedybest[k][right]dlak > leftnie jest jeszcze obliczone i ma wartość 0. Wypełniaj tabelę według szerokości albo zmniejszajleft. - Oznaczanie nierozwiązanego przedziału w tablicy memo wartością 0. Przedział balonów o wartości zero jest naprawdę wart 0, więc przy każdym odwiedzeniu jest obliczany ponownie. Użyj -1.
- W Lua i R pozycje uzupełniające biegną od 1 do
m, więc odpowiedzią jestbest[1][m].
Najczęstsze pytania3
Dlaczego Burst Balloons wybiera ostatni balon zamiast pierwszego?
Po pierwszym wybuchu jego dwa boki stają się sąsiadami, więc nadal na siebie oddziałują. Ostatni balon w przedziale pozostaje, gdy pozostałe pękają, więc jego dwa boki nigdy się nie spotykają, a każdy z nich jest niezależnym podproblemem. Gdy pęka, jego sąsiedzi wyznaczają granice przedziału.
Jaka jest złożoność czasowa problemu Burst Balloons?
Czas O(n³) i pamięć O(n²): około n²/2 przedziałów, dla każdego próba z maksymalnie n balonami jako ostatnim. Dla 300 balonów to około 4.5 × 10^6 kroków. Próbowanie każdej kolejności ma złożoność O(n · n!).
Czy problem przebijania balonów da się rozwiązać za pomocą zachłannej kolejności?
Nie. Przebicie najpierw najmniejszego balonika daje 24 dla [2, 4, 3], choć można uzyskać 33. Przebicie najpierw tego, który daje teraz najwięcej, daje 42 dla [2, 9, 2], choć przebicie najpierw 2 daje 18 + 18 + 9 = 45. Każde przebicie zmienia wartości kolejnych baloników.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def maxCoins(nums):
# Napisz kod tutajTest #1
Test #2
Test #3
Argument
nums = [2, 4, 3]
Oczekiwany wynik
33