Prosty przykład dla kogoś, kto chce zrozumieć programowanie dynamiczne [zamknięte]

Szukam zrozumiałego przykładu dla kogoś, kto chce się nauczyć programowania dynamicznego. Są tutaj dobre odpowiedzi na temat tego, czym jest programowanie dynamiczne . Sekwencja Fibonacciego jest świetnym przykładem, ale jest zbyt mała, aby zarysować powierzchnię. Wygląda na to, że jest to świetny temat do nauczenia, chociaż nie miałem jeszcze zajęć z algorytmów, mam nadzieję, że jest na mojej liście na wiosnę.

Zajrzyj na tę stronę: Problemy z praktyką programowania dynamicznego

Oto dobry tutorial zawierający 29 rozwiązanych problemów DP ze świetnym wyjaśnieniem.

Ideą programowania dynamicznego jest buforowanie (zapamiętywanie) rozwiązań podproblemów, chociaż myślę, że chodzi o coś więcej.

Istnieje wiele problemów związanych z Google Code Jam, które wymagają dynamicznego programowania, aby były wydajne. Przykłady:

Witamy w Code Jam (umiarkowany)

Oszukiwanie drzewa boolowskiego (umiarkowane)

PermRLE (twardy)

Pamiętaj, że każdy z konkursów treningowych Code Jam ma sekcję „Analiza konkursów”, w przypadku której nie możesz się doczekać rozwiązania problemu.

1. Geeks for geeks ma świetną kolekcję problemów z programowaniem dynamicznym. Uważam, że ten zestaw jest jednym z najlepszych, jeśli przygotowujesz się do rozmowy kwalifikacyjnej.
2. Jeśli potrzebujesz krótkich filmów instruktażowych dotyczących problemów z DP, możesz sprawdzić ten zestaw problemów z MIT.

Obliczanie odległości Levenshteina było jednym z pierwszych problemów, które rozwiązałem podczas programowania dynamicznego; Myślę, że pod względem złożoności jest to przyzwoity kolejny krok od sekwencji Fibonacciego.

http://en.wikipedia.org/wiki/Levenshtein_distance