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ę.
Odpowiedzi:
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)
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.
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.