W tym wykładzie przedstawimy nową technikę konstrukcji algorytmów zwaną programowaniem dynamicznym. Zasadnicza idea tej metody polega na rozbiciu danego problemu na podproblemy, rozwiązaniu ich wszystkich i zbudowaniu rozwiązania całego zadania w oparciu o uzyskane wyniki. Oczywiście nie zawsze możemy tę metodę stosować z dobrym skutkiem, gdyż nie zawsze umiemy z rozwiązań podproblemów wyciągać wnioski dotyczące rozwiązania problemu większego i nie zawsze koszt uzyskanego algorytmu jest zadowalający. Jest jednak pewna klasa problemów, w których zastosowanie tej metody daje doskonałe rezultaty. Przykłady takich problemów przedstawimy w następnych punktach tego wykładu. Rozważymy problem obliczania iloczynu ciągu macierzy i znajdowania najdłuższego wspólnego podciągu danych ciągów. W obu przypadkach narzucający się, rekurencyjny algorytm prowadzi do algorytmu o koszcie wykładniczym. Zastosowanie paradygmatu programowania dynamicznego doprowadza w obu przypadkach do skonstruowania algorytm o koszcie wielomianowym.