Czy każdy algorytm rekursywny można poprawić za pomocą programowania dynamicznego?

Question

Jestem studentem pierwszego roku studiów licencjackich, który chce dostać się do konkurencyjnego programowania.

Rekursja obejmuje definiowanie i rozwiązywanie problemów dodatkowych. Jak rozumiem, zindywidualizowane programowanie dynamiczne (dp) obejmuje zapamiętywanie rozwiązań dla problemów podrzędnych w celu zmniejszenia złożoności czasowej algorytmu.

Czy dolny dp może być użyty do poprawy wydajności każdego algorytmu rekursywnego z nakładającymi się problemami podrzędnymi? Gdzie nie działa dp i jak mogę to zidentyfikować?

Answer 1

Krótka odpowiedź brzmi: Tak.

Istnieje jednak kilka ograniczeń. Najbardziej oczywiste jest to, że rekurencyjne połączenia muszą się nakładać. To znaczy. podczas wykonywania algorytmu funkcja rekursywna musi być wywołana wiele razy z tymi samymi parametrami. Pozwala to na skrócenie drzewa rekursji poprzez zapamiętywanie. Dlatego zawsze możesz użyć funkcji zapamiętywania, aby zmniejszyć liczbę połączeń.

Jednak ta redukcja połączeń ma swoją cenę. Musisz gdzieś przechowywać wyniki. Następną oczywistą przeszkodą jest to, że musisz mieć wystarczającą ilość pamięci. Jest to spowodowane nie tak oczywistym ograniczeniem. Dostęp do pamięci zawsze wymaga trochę czasu. Najpierw musisz znaleźć miejsce, w którym zapisany jest wynik, a następnie może nawet skopiować go do wybranej lokalizacji. W niektórych przypadkach może być szybciej pozwolić rekursji obliczyć wynik zamiast ładować go skądś. Jest to jednak ściśle związane z implementacją i może nawet zależeć od systemu operacyjnego i konfiguracji sprzętu.