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.
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.
źródło