Tabulation (podejście tabelaryczne)

1. Czym jest tabulation?

Tabulation to technika DP, w której budujemy rozwiązanie iteracyjnie od dołu do góry (bottom-up), wypełniając tablicę wyników.

1.1. Porównanie z memoization:

Memoization (Top-Down):
- Rekurencja + cache
- Od problemu głównego do podproblemów
- Oblicza tylko potrzebne podproblemy

Tabulation (Bottom-Up):
- Iteracja + tablica
- Od najmniejszych podproblemów do głównego
- Oblicza wszystkie podproblemy

2. Fibonacci - tabulation

2.1. Implementacja podstawowa:

2.2. Wizualizacja tablicy:

n = 10

i=0: dp = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1: dp = [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
i=2: dp = [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0] (0+1)
i=3: dp = [0, 1, 1, 2, 0, 0, 0, 0, 0, 0, 0] (1+1)
i=4: dp = [0, 1, 1, 2, 3, 0, 0, 0, 0, 0, 0] (1+2)
i=5: dp = [0, 1, 1, 2, 3, 5, 0, 0, 0, 0, 0] (2+3)
...
i=10: dp = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Wynik: dp[10] = 55

3. Optymalizacja pamięci

3.1. Obserwacja:

Do obliczenia dp[i] potrzebujemy tylko dp[i-1] i dp[i-2].

3.2. Fibonacci z O(1) pamięcią:

Redukcja: O(n) → O(1) pamięci! ✅

4. Schody - tabulation

4.1. Problem:

n stopni, możesz wejść o 1, 2 lub 3 stopnie.
Ile jest sposobów dotarcia na szczyt?

4.2. Wzór rekurencyjny:

ways(i) = ways(i-1) + ways(i-2) + ways(i-3)

4.3. Implementacja:

4.4. Z optymalizacją pamięci:

5. Minimalna liczba monet (Coin Change)

5.1. Tabulation:

5.2. Wizualizacja tablicy:

coins = [1, 2, 5], amount = 11

i=0:  dp[0] = 0
i=1:  dp[1] = 1  (1)
i=2:  dp[2] = 1  (2)
i=3:  dp[3] = 2  (2+1)
i=4:  dp[4] = 2  (2+2)
i=5:  dp[5] = 1  (5)
i=6:  dp[6] = 2  (5+1)
i=7:  dp[7] = 2  (5+2)
i=8:  dp[8] = 3  (5+2+1)
i=9:  dp[9] = 3  (5+2+2)
i=10: dp[10] = 2 (5+5)
i=11: dp[11] = 3 (5+5+1)

Wynik: 3

6. Odtwarzanie ścieżki

6.1. Zapamiętywanie decyzji:

7. Maximum Subarray Sum (Kadane's Algorithm)

7.1. Problem:

Znajdź podtablicę o maksymalnej sumie.

Przykład: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Odpowiedź: [4, -1, 2, 1] → suma = 6

7.2. Tabulation:

7.3. Optymalizacja pamięci:

8. House Robber (Złodziej w domach)

8.1. Problem:

Jesteś złodziejem.
Każdy dom ma pewną wartość (arr[i]).
Nie możesz okraść dwóch sąsiednich domów (alarm!).

Jaka jest maksymalna łączna wartość?

Przykład: [2, 7, 9, 3, 1]
Odpowiedź: 12 (7 + 3 + 2 = 12, domy 1, 3, 4)
Albo: 12 (2 + 9 + 1 = 12, domy 0, 2, 4)

8.2. Wzór rekurencyjny:

dp[i] = max(dp[i-1], dp[i-2] + arr[i])

Albo:
- Nie okradaj domu i → dp[i-1]
- Okradaj dom i → dp[i-2] + arr[i]

8.3. Implementacja:

8.4. Optymalizacja pamięci:

9. Najdłuższa rosnąca podciąg (LIS)

9.1. Problem:

Znajdź długość najdłuższego rosnącego podciągu.

Przykład: [10, 9, 2, 5, 3, 7, 101, 18]
LIS: [2, 3, 7, 101] lub [2, 3, 7, 18]
Długość: 4

9.2. Tabulation O(n²):

10. Porównanie: Memoization vs Tabulation

11. Podsumowanie

Tabulation (Bottom-Up):

  • Iteracyjne budowanie rozwiązania
  • Od dołu do góry – od najmniejszych podproblemów
  • Tablica DP przechowuje wyniki
  • Bez rekurencji – brak narzutu stosu

Zalety:

✅ Szybsze niż memoization (brak rekurencji) ✅ O(1) na stosie (bez głębokiej rekurencji) ✅ Łatwiejsza optymalizacja pamięci ✅ Przewidywalna kolejność obliczeń

Wady:

❌ Mniej intuicyjne niż rekurencja ❌ Oblicza wszystkie podproblemy (nawet niepotrzebne) ❌ Wymaga przemyślenia kolejności wypełniania

Optymalizacja pamięci:

Porównanie:

Aspekt Memoization Tabulation
Podejście Rekurencja Iteracja ✅
Kierunek Top-Down Bottom-Up
Stos O(n) ❌ O(1) ✅
Szybkość Wolniejsze Szybsze ✅
Prostota Intuicyjne ✅ Wymaga przemyślenia
Optymalizacja Trudniejsza Łatwiejsza ✅

Kroki implementacji tabulation:

  1. Zdefiniuj dp[i] – co reprezentuje?
  2. Przypadki bazowe – dp[0], dp[1], ...
  3. Wzór rekurencyjny – dp[i] = f(dp[i-1], dp[i-2], ...)
  4. Kolejność – wypełniaj od dołu do góry
  5. Wynik – zwróć dp[n]

Przykłady:

Co dalej warto poznać:

  • Space optimization – redukcja O(n) → O(1)
  • 2D DP – problemy z dwiema zmiennymi
  • Knapsack problem – klasyczny problem DP
  • LCS/LIS – problemy sekwencyjne
  • Matrix chain – wielowymiarowy DP
Wróć do spisu lekcji