Czytałem notes on Dynamic programming i napotkałem następujący komentarz.Dynamiczne programowanie i dziel i rządź
Jeżeli podproblemów nie są niezależne, to znaczy podproblemów subsubproblems akcji, to algorytm divideand-przejęcie wielokrotnie rozwiązuje wspólne subsubproblems. Zatem, to nie więcej pracy, niż to konieczne
Co to oznacza? Czy możesz podać przykłady, aby powyższy punkt był jasny?
Autor odnosi się do faktu, że wiele algorytmów dziel i zwyciężaj ma podproblemy, które nakładają się na siebie. Rozważmy, na przykład, to bardzo prosta implementacja Fibonacciego:
int Fibonacci(int n) {
if (n <= 1) return n;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
Jeśli prześledzić połączenia wykonywane obliczyć Fibonacciego (4), otrzymujemy
Innymi słowy, wykonano 9 pełnych wywołań funkcji, ale jest tu tylko pięć unikalnych połączeń (Fibonacci od 0 do 4 włącznie). Algorytm ten mógłby być znacznie bardziej efektywny, gdyby rekurencyjne wywołania były dzielone pomiędzy podproblemami, a nie przeliczane od zera za każdym razem. Jest to jedna z kluczowych idei kryjących się za dynamicznym programowaniem.
Do obliczenia K n (n-ta liczba Fibonacciego), powyższy kod będzie łącznie 2F n + 1 - 1 rekurencyjnych. Ponieważ numery Fibonacciego szybko rosną wykładniczo, wymaga to wykładniczej dużej ilości pracy. Jednak możliwe jest wykorzystanie faktu, że wiele wywołań rekurencyjnych jest identycznych, aby uprościć to znacznie. Zamiast zaczynać od Fibonacciego (4) i pracować, zacznijmy od Fibonacciego (0) i pracujmy. W szczególności, będziemy budować tabeli (nazwijmy go FTable) o długości 5 i wypełni je w sposób następujący:
Załóżmy teraz, że chcemy obliczyć FTable [2]. Wymaga to od nas znajomości opcji FTable [0] i FTable [1], ale wiemy już o tym, ponieważ znajdują się one w tabeli.W ten sposób można ustawić
Stosując podobne rozwiązanie, można obliczyć FTable [3] ze FTable [2], a FTable [1]:
i FTable [4] ze FTable [2], a FTable [3]:
zauważyć, jak my unikał wiele nakładających wywołań cyklicznych tylko o budowaniu ich w odwrotnej kolejności! Teraz oblicza liczby Fibonacciego w czasie O (n), które jest wykładniczo szybsze niż poprzednio. Korzystając z bardziej zaawansowanej matematyki, możemy zrobić to jeszcze lepiej, ale to ilustruje, dlaczego programowanie dynamiczne może przynieść niewykonalne problemy i sprawić, że staną się nagle wykonalne.
Mam nadzieję, że to pomoże!