algorithm
Zastosowania programowania dynamicznego

Wprowadzenie

Uwagi

Liczby Fibonacciego

Liczby Fibonacciego są głównym przedmiotem programowania dynamicznego, ponieważ tradycyjne podejście rekurencyjne wykonuje wiele powtarzanych obliczeń. W tych przykładach użyję podstawowego przypadku f(0) = f(1) = 1 .

Oto przykład drzewa rekurencyjnego dla fibonacci(4) , zwróć uwagę na powtarzające się obliczenia:

Programowanie niedynamiczne Złożoność środowiska wykonawczego O(2^n) Złożoność stosu O(n)

def fibonacci(n):
    if n < 2:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

Jest to najbardziej intuicyjny sposób na napisanie problemu. Maksymalnie przestrzeń stosu będzie wynosić O(n) podczas schodzenia z pierwszej gałęzi rekurencyjnej wywołującej fibonacci(n-1) dopóki nie trafisz na przypadek podstawowy n < 2 .

Dowód złożoności środowiska wykonawczego O(2^n) który można zobaczyć tutaj: Złożoność obliczeniowa sekwencji Fibonacciego . Należy przede wszystkim zauważyć, że środowisko wykonawcze ma charakter wykładniczy, co oznacza, że środowisko wykonawcze podwoi się w każdym kolejnym okresie, fibonacci(15) zajmie dwa razy więcej niż fibonacci(14) .

Zapamiętane O(n) Złożoność środowiska wykonawczego, O(n) Złożoność przestrzeni, O(n) Złożoność stosu

memo = []
memo.append(1) # f(1) = 1
memo.append(1) # f(2) = 1

def fibonacci(n):
    if len(memo) > n:
        return memo[n]

    result = fibonacci(n-1) + fibonacci(n-2)
    memo.append(result) # f(n) = f(n-1) + f(n-2)
    return result

W zapamiętywanym podejściu wprowadzamy tablicę, którą można traktować jak wszystkie poprzednie wywołania funkcji. memo[n] lokalizacyjna memo[n] jest wynikiem wywołania funkcji fibonacci(n) . Pozwala nam to na wymianę złożoności przestrzeni O(n) na środowisko wykonawcze O(n) ponieważ nie musimy już obliczać zduplikowanych wywołań funkcji.

Iteracyjne programowanie dynamiczne O(n) Złożoność środowiska wykonawczego, O(n) Złożoność przestrzeni, Brak stosu rekurencyjnego

def fibonacci(n):
    memo = [1,1] # f(0) = 1, f(1) = 1

    for i in range(2, n+1):
         memo.append(memo[i-1] + memo[i-2])

    return memo[n]

Jeśli podzielimy problem na podstawowe elementy, zauważysz, że do obliczenia fibonacci(n) potrzebujemy fibonacci(n-1) i fibonacci(n-2) . Możemy również zauważyć, że nasz przypadek podstawowy pojawi się na końcu tego drzewa rekurencyjnego, jak pokazano powyżej.

Na podstawie tych informacji warto teraz obliczyć rozwiązanie wstecz, zaczynając od przypadków podstawowych i pracując w górę. Teraz, aby obliczyć fibonacci(n) , najpierw obliczamy wszystkie liczby Fibonacciego do i przez n .

Główną zaletą jest to, że wyeliminowaliśmy teraz stos rekurencyjny, zachowując czas działania O(n) . Niestety nadal mamy złożoność przestrzeni O(n) ale można to również zmienić.

Zaawansowane programowanie dynamiczne iteracyjne O(n) Złożoność środowiska wykonawczego, O(1) Złożoność przestrzeni, Brak stosu rekurencyjnego

def fibonacci(n):
    memo = [1,1] # f(1) = 1, f(2) = 1

    for i in range (2, n):
        memo[i%2] = memo[0] + memo[1]

    return memo[n%2]

Jak wspomniano powyżej, iteracyjne podejście do programowania dynamicznego rozpoczyna się od przypadków podstawowych i działa do wyniku końcowego. Kluczową obserwacją, aby dokonać złożoności przestrzeni do O(1) (stała), jest ta sama obserwacja, którą zrobiliśmy dla stosu rekurencyjnego - potrzebujemy tylko fibonacci(n-1) i fibonacci(n-2) do zbudowania fibonacci(n) . Oznacza to, że musimy zapisać wyniki tylko dla fibonacci(n-1) i fibonacci(n-2) w dowolnym punkcie naszej iteracji.

Aby zapisać te 2 ostatnie wyniki, używam tablicy o rozmiarze 2 i po prostu odwracam, do którego indeksu przypisuję, używając i % 2 które będą naprzemiennie: 0, 1, 0, 1, 0, 1, ..., i % 2 .

Dodaję oba indeksy tablicy razem, ponieważ wiemy, że dodawanie jest przemienne ( 5 + 6 = 11 i 6 + 5 == 11 ). Wynik jest następnie przypisywany do starszego z dwóch miejsc (oznaczonych przez i % 2 ). Ostateczny wynik jest następnie zapisywany w pozycji n%2

Notatki

• Ważne jest, aby pamiętać, że czasami najlepiej jest wymyślić iteracyjne zapamiętane rozwiązanie dla funkcji, które wykonują duże obliczenia wielokrotnie, ponieważ utworzysz pamięć podręczną odpowiedzi na wywołania funkcji, a kolejne wywołania mogą być O(1) jeśli zostało już obliczone.