Schemat przedziałowego DP i kolejność wypełniania

DP przedziałowe to wzorzec programowania dynamicznego, w którym stan dp[i][j] reprezentuje optymalną odpowiedź dla podproblemu obejmującego indeksy od i do j. Kluczowa obserwacja polega na tym, że najpierw rozwiązujemy mniejsze przedziały, a następnie stopniowo rozszerzamy rozwiązanie na cały zakres. Ten wzorzec naturalnie odwzorowuje problemy takie jak mnożenie łańcucha macierzy, partycjonowanie palindromu i rozbijanie balonów, w których granicami podproblemu są lewy i prawy koniec zakresu.

W DP przedziałowym stanem jest dp[i][j], gdzie i <= j. Przypadkami bazowymi są przedziały zawierające jeden element: dp[i][i]. Można je rozwiązać bezpośrednio — na przykład pojedyncza macierz ma koszt mnożenia równy zero. Przedziały zawierające dwa elementy, dp[i][i+1], również często mają proste rozwiązania. Wypełniamy tabelę dla rosnących długości przedziałów, zaczynając od długości 1 i kończąc na n.

Kluczowym szczegółem w DP przedziałowym jest kolejność wypełniania. Musimy obliczyć wszystkie przedziały o długości L, zanim obliczymy przedziały o długości L+1, ponieważ dłuższy przedział zależy od krótszych podprzedziałów. Pętla zewnętrzna przechodzi po długościach przedziałów od 2 do n, pętla środkowa ustawia lewą granicę i, a prawą granicę wyznaczamy jako j = i + L - 1.

Klasycznym problemem DP przedziałowego jest mnożenie łańcucha macierzy: mając macierze o wymiarach dims[0..n], należy znaleźć minimalną liczbę mnożeń skalarnych potrzebnych do obliczenia iloczynu. Mnożenie macierzy A(p×q) przez B(q×r) kosztuje p*q*r operacji. dp[i][j] oznacza minimalny koszt pomnożenia macierzy od i do j. Punkt podziału k określa, gdzie sekwencja zostaje podzielona na dwa podłańcuchy.

Prześledźmy przykład mnożenia łańcucha macierzy o wymiarach [10, 30, 5, 60], reprezentujący trzy macierze: A(10×30), B(30×5) i C(5×60). Dla dp[0][2] próbujemy podziału w k=0: dp[0][0] + dp[1][2] + 10×30×60 = 0 + 9000 + 18000 = 27000, a także w k=1: dp[0][1] + dp[2][2] + 10×5×60 = 1500 + 0 + 3000 = 4500. Zatem dp[0][2] = 4500, co osiągamy, mnożąc najpierw AB.

Podczas obliczania dp[i][j] odwołujemy się do dp[i][k] oraz dp[k+1][j] dla każdego k w zakresie [i, j-1]. Oba podprzedziały mają ściśle mniejszą długość niż [i, j]. Iterowanie po długościach od najmniejszych do największych gwarantuje, że wszystkie wymagane podprzedziały zostaną obliczone, zanim będą potrzebne. Jest to podstawowy argument poprawności kolejności wypełniania w DP przedziałowym — krótsze przedziały zawsze są zależnościami dłuższych.

DP przedziałowe można również zaimplementować odgórnie z memoizacją. Piszemy funkcję rekurencyjną solve(i, j), która zwraca optymalny koszt dla przedziału [i, j], a wyniki zapisujemy w słowniku. Rekurencja automatycznie obsługuje kolejność wypełniania. Podejście top-down często ułatwia rozumowanie, ale może wiązać się z narzutem wywołań funkcji; podejście bottom-up jest w praktyce szybsze dla dużych danych wejściowych.

DP przedziałowe ma O(n²) stanów (wszystkie pary (i, j)), a każdy stan iteruje po O(n) punktach podziału, co daje łącznie O(n³) czasu. Pamięć zajmowana przez tabelę DP to O(n²). W przypadku mnożenia łańcucha 100 macierzy oznacza to 1 000 000 operacji — jest to bardzo łatwe do wykonania. Ten wzorzec pojawia się w wielu trudnych zadaniach LeetCode i jest często wybierany podczas rozmów kwalifikacyjnych FAANG ze względu na swoją nieoczywistą strukturę.

Aby odtworzyć rzeczywiste nawiasowanie (a nie tylko koszt), należy przechowywać osobną tabelę split[i][j], rejestrującą wartość k, dla której w danym stanie osiągnięto minimum. Następnie odczytujemy podziały rekurencyjnie: reconstruct(i, j) wypisuje optymalne grupowanie, wywołując się rekurencyjnie dla [i, split[i][j]] oraz [split[i][j]+1, j]. Technika ta ma zastosowanie we wszystkich problemach DP przedziałowego.

Uniwersalny szablon DP przedziałowego składa się z trzech części: (1) zainicjalizowania przypadków bazowych dla pojedynczych elementów, (2) iterowania po rosnących długościach i, dla każdej długości, iterowania po prawidłowych lewych granicach oraz wyznaczenia prawej granicy, a także (3) iterowania dla każdego przedziału po wszystkich punktach podziału i zastosowania zależności rekurencyjnej właściwej dla danego problemu. Jedyną zmienianą między problemami częścią jest wzór rekurencyjny wewnątrz najbardziej zagnieżdżonej pętli.

Problemy wykorzystujące DP przedziałowe obejmują: mnożenie łańcucha macierzy (minimalizacja liczby operacji), rozbijanie balonów (maksymalizacja liczby monet), Dziwnego drukarza (minimalizacja liczby operacji drukowania), triangulację wielokąta o minimalnym wyniku oraz partycjonowanie palindromu II. Każdy z nich korzysta z tego samego szkieletu kolejności wypełniania, ale z innej zależności rekurencyjnej. Należy rozpoznać ten wzorzec, gdy problem wymaga znalezienia optymalnej wartości dla zakresu lub sekwencji, którą można podzielić w dowolnym punkcie wewnętrznym.

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

W tej lekcji nauczyłeś się, że: DP przedziałowe wykorzystuje dp[i][j] do reprezentowania optymalnej odpowiedzi dla zakresu, kolejność wypełniania musi uwzględniać rosnące długości przedziałów, aby najpierw obliczyć podprzedziały, a uniwersalny szablon ma złożoność czasową O(n³) i pamięciową O(n²). Następnie poznamy najdłuższy palindromiczny podciąg i podłańcuch, korzystając właśnie z tego wzorca.