Unikalne ścieżki i minimalna suma ścieżki na siatkach

Unique Paths (LeetCode 62) pyta: w siatce m×n ile jest różnych ścieżek z lewego górnego do prawego dolnego rogu, jeśli można poruszać się tylko w prawo lub dół? Dla siatki 3×7 odpowiedzią jest 28. Kluczowa obserwacja jest taka, że każda ścieżka do komórki (i,j) musi prowadzić z (i-1,j) (z góry) albo z (i,j-1) (z lewej), co prowadzi do naturalnego sformułowania DP 2D.

Zdefiniuj dp[i][j] jako liczbę ścieżek do komórki (i,j). Pierwszy wiersz i pierwsza kolumna składają się wyłącznie z jedynek, ponieważ do każdej komórki w górnym wierszu lub skrajnej lewej kolumnie prowadzi tylko jedna ścieżka. Dla pozostałych komórek: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Tabelę należy wypełniać wiersz po wierszu, a odpowiedzią jest dp[m-1][n-1]. Złożoność czasowa: O(m×n), pamięciowa: O(m×n), którą można zmniejszyć do O(n).

Ponieważ dp[i][j] zależy tylko od bieżącego i poprzedniego wiersza, pełną tabelę 2D można zastąpić pojedynczą tablicą 1D. Należy zainicjalizować wszystkie wartości jako 1, a następnie dla każdego wiersza aktualizować je w miejscu: dp[j] += dp[j-1]. Po przetworzeniu wiersza i wartość dp[j] odpowiada wartości dp[i][j] w tabeli 2D. Jest to często stosowany schemat optymalizacji w problemach DP 2D.

Unique Paths II (LeetCode 63) dodaje do siatki przeszkody (komórki oznaczone wartością 1). Każda ścieżka przechodząca przez przeszkodę jest niepoprawna, dlatego dp[i][j] = 0, jeśli obstacle[i][j] == 1. W przeciwnym razie rekurencja pozostaje taka sama: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Zablokowany początek lub koniec od razu daje wynik 0. Należy starannie zainicjalizować przypadki bazowe — gdy w pierwszym wierszu lub kolumnie pojawi się 1, wszystkie kolejne komórki w tym wierszu lub tej kolumnie mają wartość 0.

Minimum Path Sum (LeetCode 64) pyta: dla siatki m×n wypełnionej nieujemnymi liczbami należy znaleźć ścieżkę z lewego górnego do prawego dolnego rogu, która minimalizuje sumę wszystkich liczb na ścieżce (poruszając się tylko w prawo lub w dół). Na przykład w przypadku [[1,3,1],[1,5,1],[4,2,1]] ścieżka 1→3→1→1→1 daje sumę 7. Stan DP jest taki sam jak w przypadku Unique Paths, ale w rekurencji dodawanie zastępuje się operacją minimum.

Zdefiniuj dp[i][j] jako minimalny koszt dotarcia do komórki (i,j). Przypadek bazowy: dp[0][0] = grid[0][0]. Pierwszy wiersz: dp[0][j] = dp[0][j-1] + grid[0][j] (jedyna droga prowadzi z lewej). Pierwsza kolumna: dp[i][0] = dp[i-1][0] + grid[i][0] (jedyna droga prowadzi z góry). Przypadek ogólny: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Jest to bezpośrednie zastosowanie zasady optymalności.

Jeśli można modyfikować siatkę wejściową, można aktualizować ją w miejscu, aby uniknąć przydzielania osobnej tabeli DP. Zmniejsza to pamięć dodatkową do O(1) (nie licząc danych wejściowych). Podczas rozmowy kwalifikacyjnej może paść pytanie o tę optymalizację — przed jej zastosowaniem należy ustalić, czy modyfikowanie danych wejściowych jest dozwolone. Jeśli nie, sztuczka z jednowymiarową tablicą kroczącą pozwala uzyskać pamięć O(n) bez modyfikowania danych wejściowych.

Triangle (LeetCode 120) wymaga znalezienia minimalnej sumy ścieżki od góry do dołu w tablicy reprezentującej trójkąt, gdzie każdy krok prowadzi do sąsiedniej liczby w poniższym wierszu. Najczytelniejsze jest DP od dołu: należy rozpocząć od przedostatniego wiersza i dla każdej komórki dodać minimum z dwóch komórek znajdujących się bezpośrednio poniżej. Dzięki temu nie trzeba śledzić indeksów początkowych, a odpowiedź naturalnie wędruje do wierzchołka.

Dungeon Game (LeetCode 174) pyta o minimalne początkowe zdrowie potrzebne do uratowania księżniczki znajdującej się w prawym dolnym rogu siatki zawierającej komórki z wartościami ujemnymi (obrażenia) i dodatnimi (leczenie). Należy poruszać się w prawo lub w dół. Sztuczka polega na wypełnieniu tabeli DP od końca (od prawego dolnego do lewego górnego rogu) i obliczeniu minimalnej liczby punktów zdrowia potrzebnych w każdej komórce. Dla każdej komórki: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]). Zdrowie musi zawsze wynosić co najmniej 1.

Problemy DP na siatkach mają tę samą strukturę, ale różnią się kierunkiem wypełniania i operacją przejścia: Unique Paths używa dodawania (zlicza wszystkie sposoby). Min Path Sum używa minimum (optymalizuje koszt). Dungeon Game wypełnia tabelę od końca (oblicza zdrowie potrzebne w przyszłości). Podczas rozwiązywania nowego problemu DP na siatce należy zadać sobie trzy pytania: (1) Co reprezentuje każda komórka? (2) W jakim kierunku należy wypełniać tabelę? (3) Jaka operacja łączy wartości sąsiednich komórek? Odpowiedzi na te trzy pytania ujawniają całe rozwiązanie.

Wszystkie omówione problemy DP na siatkach mają złożoność czasową O(m×n). Zużycie pamięci wynosi od O(m×n) dla pełnej tabeli, przez O(n) przy użyciu jednowymiarowej tablicy kroczącej, aż po O(1) pamięci dodatkowej, gdy siatkę można modyfikować w miejscu. Podczas rozmowy kwalifikacyjnej należy wspomnieć o optymalizacji pamięci do O(n) po przedstawieniu rozwiązania O(m×n) — pokazuje to świadomość kompromisów. W przypadku wszystkich problemów warto również rozważyć, czy istnieje proste rozwiązanie zachłanne (na przykład wzór matematyczny dla Unique Paths).

Sprawdź swoją wiedzę na temat zagadnień Data Structures & Algorithms — Coding Interview Prep omawianych w tej lekcji.

W tej lekcji nauczyli się Państwo, że: Unique Paths wypełnia tabelę 2D za pomocą dp[i][j] = dp[i-1][j] + dp[i][j-1] i można obliczyć ten problem w czasie O(1) przy użyciu kombinatoryki, Min Path Sum wykorzystuje tę samą strukturę, ale zastępuje dodawanie operacją min w celu znalezienia optymalnego kosztu ścieżki oraz wszystkie problemy DP na siatkach mają wspólny schemat: zdefiniowanie stanu dla każdej komórki i wybór operatora przejścia (sum, min, max). Następnie omówimy Longest Common Subsequence, używając DP 2D dla dwóch sekwencji.