Burst Balloons: odwrócone przedziałowe DP

Dla n balonów o wartościach nums wybicie balonu i daje nums[i-1] * nums[i] * nums[i+1] monet (jest to iloczyn jego wartości i wartości jego aktualnych sąsiadów). Po jego wybiciu sąsiednie balony stają się bezpośrednimi sąsiadami. Należy znaleźć maksymalną liczbę monet, jaką można zebrać, wybijając wszystkie balony. Naiwna symulacja jest trudna, ponieważ wybijanie zmienia sąsiadów — odwrócone DP na przedziałach elegancko omija tę trudność.

Jeśli spróbujemy zdefiniować dp[i][j] jako maksymalną liczbę monet za wybicie balonów z zakresu [i, j] i zastanowimy się, który balon wybić jako pierwszy, pojawi się problem: wybicie balonu k jako pierwszego oznacza, że nums[k-1] i nums[k+1] muszą być jego aktualnymi sąsiadami — ale te balony mogą zostać wybite później, przez co sąsiedztwo będzie się dynamicznie zmieniać. W kierunku od początku trudno poprawnie i przejrzyście zdefiniować stan.

Sztuczka polega na rozważeniu, który balon zostanie wybity jako ostatni w przedziale [i, j]. Gdy balon k jest ostatnim wybitym balonem w [i, j], wszystkie pozostałe balony z [i, j] zostały już usunięte. Zatem sąsiadami balonu k są dokładnie nums[i-1] i nums[j+1] — balony graniczne znajdujące się tuż poza przedziałem. Dzięki temu obliczenie liczby monet za ostatnie wybicie jest jednoznaczne: nie zależy od kolejności wcześniejszych wybić.

Dodaj balony wartownikowe: umieść wartość 1 na początku i na końcu nums, aby otrzymać nums = [1] + nums + [1]. Zdefiniuj dp[i][j] jako maksymalną liczbę monet za wybicie wszystkich balonów znajdujących się ściśle między indeksami i i j (bez tych indeksów), gdzie nums[i] i nums[j] są pozostałymi balonami granicznymi. Rekurencja: dla każdego kandydata na ostatni balon k w (i, j): dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]).

Uzupełniamy tablicę wartownikami, inicjalizujemy tabelę DP zerami (pusty przedział = 0 monet), a następnie wypełniamy ją dla rosnącej długości przedziału. Ostateczna odpowiedź to dp[0][n+1], reprezentująca maksymalną liczbę monet za wybicie wszystkich oryginalnych balonów przy założeniu, że wartowniki są stałymi granicami.

Dla [3, 1, 5, 8] po uzupełnieniu otrzymujemy [1, 3, 1, 5, 8, 1] (indeksy 0–5). Szukamy dp[0][5]. Dla przedziałów length=2 (jeden balon wewnątrz): 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. Rozwijając rozwiązanie, otrzymujemy optimum, wybijając balon 1 jako ostatni spośród {3,1,5,8}, po wcześniejszym wybiciu jego sąsiadów — łącznie 167 monet.

Istnieje O(n²) przedziałów, a dla każdego z nich sprawdzamy O(n) punktów podziału, co daje złożoność czasową O(n³). Pamięć zajmowana przez tabelę DP wynosi O(n²). Dla n = 500 balonów oznacza to 125 milionów operacji — jest to wykonalne przy ograniczeniach typowych dla rozmów rekrutacyjnych. Uzupełnienie tablicy wartownikami upraszcza obsługę granic: bez niego trzeba byłoby jawnie sprawdzać, czy i-1 i j+1 mieszczą się w zakresie.

To samo rozwiązanie można zapisać od góry w dół z użyciem @lru_cache, co może ułatwić jego wyprowadzenie podczas rozmowy rekrutacyjnej. Zdefiniuj solve(i, j) jako maksymalną liczbę monet w otwartym przedziale (i, j). Funkcja wypróbowuje wszystkie wartości k jako ostatni wybijany balon i zapamiętuje wyniki. Oba podejścia mają identyczną złożoność czasową i pamięciową.

Częstym błędem jest zdefiniowanie dp[i][j] jako liczby monet w sytuacji, gdy pierwszy balon z [i,j] zostaje wybity, a nie jako balonu wybijanego jako ostatni. To nie działa, ponieważ obliczenie liczby monet za pierwsze wybicie zależy od sąsiednich balonów, które nie zostały jeszcze wybite — a ich stan zmienia się w miarę postępu algorytmu. W DP na przedziałach należy zawsze myśleć o ostatnim elemencie, gdy granice zależą od pozostałych elementów.

Wartowniki o wartości 1 wybiera się dlatego, że są elementami neutralnymi mnożenia. Gdy balon graniczny jest ostatnim wybijanym balonem, liczba monet wynosi boundary * last * boundary = 1 * last * 1 = last. Użycie wartości 0 dałoby 0 monet (czyli błędny wynik), a inne wartości zniekształciłyby obliczenia. Sztuczka z wartownikami w elegancki sposób ujednolica wszystkie przypadki brzegowe bez specjalnego traktowania skrajnego lewego i skrajnego prawego balonu.

W standardowym DP na przedziałach (np. w problemie mnożenia łańcucha macierzy) punkt podziału k wskazuje miejsce, w którym dzielimy problem na dwa podproblemy rozwiązywane niezależnie. W problemie Burst Balloons k oznacza balon wybijany jako ostatni w przedziale, dzięki czemu dwa podprzedziały [i,k] i [k,j] stają się niezależne, pod warunkiem że k nadal znajduje się na granicy. To odwrócone spojrzenie jest pomysłową obserwacją, która pozwala rozwiązać problem Burst Balloons za pomocą DP na przedziałach.

Sprawdź swoje zrozumienie koncepcji Data Structures & Algorithms — Coding Interview Prep z tej lekcji.

W tej lekcji poznali Państwo: dlaczego symulacja w przód zawodzi, ponieważ przebijanie balonów w nieprzewidywalny sposób zmienia sąsiadów, dlaczego spostrzeżenie wynikające z odwrócenia procesu definiuje k jako ostatni balon przebity w przedziale, dzięki czemu sąsiadami stają się nums[i] i nums[j] oraz dlaczego zależność dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]) z dodaniem wartości wartowników daje rozwiązanie o złożoności O(n³). Następnie przejdziemy do programowania dynamicznego dla problemu plecakowego, zaczynając od klasycznego problemu plecakowego 0/1 i jego optymalizacji pamięci.