Pochopení dynamického programování: Průvodce efektivním řešením složitých problémů

DP znamená „Dynamické programování“. Je to metoda řešení složitých problémů jejich rozdělením na menší dílčí problémy, řešením každého dílčího problému pouze jednou a uložením řešení dílčích problémů, aby se předešlo nadbytečným výpočtům. menší kusy, řešení každého kusu nezávisle a pak kombinování řešení kusů, aby se vyřešil původní problém. Tím se můžeme vyhnout nadbytečným výpočtům a vyřešit problém efektivněji.

DP je zvláště užitečné pro řešení problémů, které mají překrývající se dílčí problémy, kde se stejný dílčí problém může vyskytnout vícekrát s různými vstupy. Uložením řešení těchto dílčích problémů se můžeme vyhnout jejich vícenásobnému přepočítávání a místo toho použít uložená řešení k rychlejšímu vyřešení původního problému. dílčí problémy a optimální řešení většího problému lze sestavit z optimálních řešení dílčích problémů.
* Překrývající se dílčí problémy: Stejný dílčí problém se může vyskytnout vícekrát s různými vstupy.
* Rekurze: Problém lze vyřešit rekurzivně rozbitím rozdělí se na menší kousky a vyřeší každý díl nezávisle.……Příklady DP problémů zahrnují Fibonacciho posloupnost, nejkratší cestu v grafu a nejdelší společnou podsekvenci ve dvou řetězcích.