Jak rozpoznajesz problem jako odpowiedni do programowania dynamicznego?

Ostatnio czytałem o programowaniu dynamicznym. Chciałbym usłyszeć od kogoś, kto zaczął od zera, a teraz jest całkiem dobry w identyfikowaniu i rozwiązywaniu problemów z DP. Mam problemy z identyfikacją tych problemów jako DP i sformułowaniem zwięzłego rozwiązania.

Przeszedłem przez większość problemów DP dla początkujących i zasobów MIT itp

Pochodzę z fizyki, a więc z wielu matematyki. Łatwo dostrzegam problemy dobrze dopasowane do rozwiązań programowania rekurencyjnego / dynamicznego, znajdując podobieństwa z dowodem indukcyjnym .

Dowód indukcyjny składa się z dwóch części:

• udowadniasz, że jeśli coś jest prawdziwe dla iteracji N, to dotyczy to również iteracji N + 1
• udowodnisz, że dotyczy to iteracji 1

W programowaniu rekurencyjnym / programowaniu dynamicznym:

• rozpoznajesz warunek wyjścia (na przykład sztywno podłączysz rozwiązanie dla iteracji 1)
• obliczasz rozwiązanie dla iteracji N, biorąc pod uwagę rozwiązanie dla iteracji N-1

Tak więc, jak odpowiedzieli inni, jest to kwestia doświadczenia i wybrania wskazówek, ale możesz ponownie użyć innych umiejętności, aby cię poprowadzić. Następnie musisz zawsze mieć dwie części, o których wspomniałem: jeśli nie, to nie będzie działać.

Na przykład, aby wygenerować wszystkie permutacje zestawu:

• warunek wyjścia: jeśli masz tylko jeden element, zwróć go
• rekurencja: permutacje zestawu N elementów to N zestawów permutacji, które otrzymujesz poprzez wybranie każdego elementu i połączenie ze wszystkimi zestawami N-1 (wielu) permutacji podzbioru, które otrzymujesz przez usunięcie elementu.

Większość problemów z dynamicznym programowaniem można rozwiązać poprzez zapamiętywanie. Zapamiętywanie jest zwykle bardziej intuicyjne i łatwiejsze do kodowania. Pomocne może być myślenie w kategoriach zapamiętywania zamiast DP.

Zwykle łatwiej jest zrozumieć, czy problem jest odpowiedni do zapamiętywania (kroki są takie same jak odpowiedź Slivvza , ale myślę, że zmiana mentalna jest nieco krótsza). Jednak po rozwiązaniu problemu przez zapamiętywanie możesz sprawdzić, w jaki sposób pamięć podręczna jest zapełniana, a następnie wypełnić ją w kolejności, bez rekurencji ... co zmienia algorytm w algorytm programowania dynamicznego.

TL; DR; wersja: Łatwiej zrozumieć dynamiczne programowanie w zakresie zapamiętywania.

Zobacz także StackOverflow: Programowanie dynamiczne i zapamiętywanie: podejścia oddolne vs odgórne .

Programowanie dynamiczne to definitywnie dwie rzeczy:

1. Optymalna podbudowa
   Większe rozwiązania można uzyskać z mniejszych rozwiązań; rozwiązywanie nie jest dwukierunkowe.

2. Nakładające się na siebie podproblemy
   Małe rozwiązania zostaną ponownie wykorzystane wiele razy. Jeśli podproblemy w ogóle się nie pokrywają, nie zyskujesz na DP / zapamiętywaniu; co masz jest podział i przejęcie zamiast.

Ogólne podejście do problemów związanych z DP:

• Napisz naiwną rekurencyjną lub iteracyjną wersję, która działa.

• Zauważ, że funkcja wykonuje zbędną pracę.

• Znajdź sposób na uniknięcie zbędnej pracy, często przez zapamiętywanie.

Nigdy nie wdrożyłem ani jednego dynamicznego solvera programistycznego - moim doświadczeniem jest matematyka / fizyka / obliczenia numeryczne, a nie CS - jeszcze kilka lat temu, kiedy zacząłem robić problemy z Project Euler . Rozwiązane tam problemy DP (np. 76 , 158 , 161 , 242, ale jest ich o wiele więcej), okazało się być moim ulubionym rodzajem. Zdecydowanie lepiej radzisz sobie z rozpoznawaniem, kiedy będzie to przydatna technika: po prostu szukaj rzeczy, które wydają się być możliwe do rozwiązania za pomocą pewnego rodzaju rekurencyjnego, dzielącego i podbijającego podejścia, w którym można również oswoić eksplozję ścieżek wymagających do zbadania przez rozpoznanie powtarzających się podproblemów i ponowne wykorzystanie wcześniej obliczonych wyników; umiejętność zidentyfikowania minimalnego wektora stanu do zapamiętania - i co nieistotnej „historii” można usunąć - jest kluczowym krokiem.