Programowanie dynamiczne, podejście zachłanne i podciągi

W Bloku 03 zaimplementowaliśmy rekurencyjną funkcję Fibonacciego o złożoności O(2ⁿ) — ponieważ te same podproblemy (np. fib(30)) są liczone wielokrotnie. Programowanie dynamiczne (PD) rozwiązuje ten problem, zapamiętując (memoizując) już obliczone wyniki.

def fib_pd(n, pamiec={}): if n in pamiec: return pamiec[n] if n <= 1: return n wynik = fib_pd(n - 1, pamiec) + fib_pd(n - 2, pamiec) pamiec[n] = wynik return wynik # złożoność spada z O(2ⁿ) do O(n)!

2. Najdłuższy wspólny podciąg (LCS)

Klasyczny problem PD: dla dwóch ciągów znaków znajdź najdłuższy podciąg (niekoniecznie spójny) występujący w obu. Rozwiązanie buduje tablicę dwówymiarową dp, gdzie dp[i][j] to długość LCS dla pierwszych i znaków pierwszego i pierwszych j znaków drugiego ciągu.

def lcs(a, b): n, m = len(a), len(b) dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, m + 1): if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) return dp[n][m] # lcs("ALGORYTM", "LOGIKA") -> 4 (np. "LOGA")

3. Podejście zachłanne (greedy)

Algorytm zachłanny podejmuje w każdym kroku decyzję lokalnie najlepszą, bez cofania się — i licząc na to, że suma lokalnie optymalnych wyborów da rozwiązanie globalnie optymalne. Działa to tylko dla pewnych problemów!

# wydawanie reszty (dla nominałów 1, 2, 5, 10, 20, 50) def wydaj_reszte(kwota, nominaly=[50, 20, 10, 5, 2, 1]): wynik = {} for nominal in nominaly: ile = kwota // nominal if ile > 0: wynik[nominal] = ile kwota -= ile * nominal return wynik # wydaj_reszte(73) -> {50: 1, 20: 1, 2: 1, 1: 1}

Kiedy zachłanność zawodzi

Dla nominałów [1, 3, 4] i kwoty 6, algorytm zachłanny wyda 4+1+1 (3 monety), podczas gdy optymalnie można 3+3 (2 monety)! Zachłanność działa poprawnie tylko dla pewnych zestawów nominałów (m.in. polskiego systemu monet) — ogólnie problem wydawania reszty wymaga PD.

4. Podciągi o zadanych własnościach

Algorytm Kadane'a znajduje maksymalną sumę spójnego (ciągłego) podciągu w czasie liniowym O(n):

def maks_suma_podciagu(tab): najlepsza = biezaca = tab[0] for x in tab[1:]: biezaca = max(x, biezaca + x) najlepsza = max(najlepsza, biezaca) return najlepsza # maks_suma_podciagu([-2, 1, -3, 4, -1, 2, 1, -5, 4]) -> 6 (podciąg [4,-1,2,1])

5. Ćwiczenia praktyczne

Ćwiczenie 1 — najdłuższy niemalejący podciąg

Zaprojektuj (na kartce lub w kodzie) algorytm PD znajdujący długość najdłuższego niemalejącego podciągu w tablicy liczb, np. dla [3, 1, 4, 1, 5, 9, 2, 6] wynik to 4 (podciąg 1,4,5,9 lub 1,1,5,9).

Ćwiczenie 2 — zachłanność kontra PD

Zaimplementuj rozwiązanie problemu wydawania reszty metodą PD (przeszukując wszystkie możliwe nominały dla każdej kwoty od 0 do docelowej) i porównaj wynik z wersją zachłanną dla nominałów [1, 3, 4] i kwoty 6.

Sprawdź wiedzę

1. Jak programowanie dynamiczne przyspiesza obliczanie ciągu Fibonacciego?

Zamienia rekurencję na pętlę while Zapamiętuje (memoizuje) wyniki już obliczonych podproblemów Używa notacji ONP

2. Czy algorytm zachłanny zawsze daje optymalne rozwiązanie problemu wydawania reszty?

Tak, zawsze Nie, zależy to od zestawu dostępnych nominałów Tylko dla kwot parzystych

3. Jaką złożoność czasową ma algorytm Kadane'a znajdujący maksymalną sumę spójnego podciągu?

O(n²) O(n) O(2ⁿ)

1. Problem: naiwna rekurencja Fibonacciego