Programowanie dynamiczne

Czesc, spotkal sie ktos z was na studiach lub gdzie indziej z programowaniem dynamicznym ? Pytam bo nie do konca to rozumie ;p

Na wazniaku jest to dobrze opisane. http://wazniak.mimuw.edu.pl/index.php ?title=Algorytmy_i_struktury_danych/Wst%C4%99p:_elementarne_techniki_algorytmiczne_i_struktury_danych

Ale ty jestes madry jak rozumiesz to co jest na wazniaku niby tam jest wieksosc zagadnien ze studiow ale ja po pierwszym przeczytaniu sie poddaje ;p


Ale dzieki za odpowiedz

Programowanie dynamiczne to po prostu rozwiązywanie problemu na podstawie rozwiązanych podproblemów.
Wystarczy, że zrozumiesz jakiś przykład.
http://pl.wikipedia.org/wiki/Najdłuższy_wspólny_podciąg - sekcja "Algorytm odtwarzający NWP"

Jak chcesz znaleźć najdłuższy wspólny podciąg dla 2 ciągów to robisz sobie tablicę [długość 1 słowa][długość 2 słowa] i zakładasz, że tab[a1][a2] to odpowiedź dla pierwszych a1 liter pierwszego słowa i pierwszych a2 liter drugiego słowa i po prostu wypełniasz ją od początku rozwiązując coraz większe podproblemy - tzn znając odpowiedź dla tab[a1][a2] łatwo możesz określić odpowiedź dla tab[a1+1][a2]. Na końcu ostatni element czyli tab[długość 1 słowa][długość 2 słowa] (indeksowane od 1) to odpowiedź dla 2 całych słow.

rozwiązywanie problemu na podstawie rozwiązanych podproblemów

Takie postawienie sprawy jest nieco nieintuicyjne.

Bo defakto chodzi o to, żeby strukturę na, której się operuję, najpierw rozwalić w drobny mak i później przeprowadzać tą operację na tym co zostało i na koniec stopniowo to składać w całość.

Takie postawienie sprawy jest nieco nieintuicyjne.

Niby dlaczego nieintuicyjne? Właśnie to jest najprostsza definicja, którą jest w stanie zrozumieć każdy. Rozbijasz problem na podproblemy, które pozwalają Ci rozwiązać główny problem. Wiadomo, że nikt nie będzie tu pisał obszernej, pełnej definicji tej techniki bo by zajęła trochę sporo miejsca.

Programowanie dynamiczne opiera się na podziale rozwiązywanego problemu na podproblemy względem kilku parametrów. W odróżnieniu od techniki dziel i zwyciężaj podproblemy w programowaniu dynamicznym nie są na ogół rozłączne.

I tyle.

Rozbijasz problem na podproblemy

I teraz wszystko zależy od tego co się rozumie pod pojęciem podproblem. Nie każdy się domyśli się, że chodzi o wykonanie operacji na podstrukturze.

A moge wam podac przyklad? Podobno jest on jednym z prostszych ale i tak nie wiem jak go ta metoda rozwiazac ;p