16. óra
A dinamikus programozás, mint algoritmus tervezési elv
Optimalizálási feladatok gyakran kezelhetők a dinamikus programozásnak nevezett elv segítségével. Ez a következőkből áll:
- Meghatározzuk az optimumot egy rekurzív függvény segítségével.
- Felgyorsítjuk a rekurziót a következő módon: egy tömbben tároljuk a már kiszámított függvényértékeket, és ha rekurzió egy ága már korábban kiszámított értéket kér, akkor azt a tömbből "vesszük elő", ahelyett, hogy újra meghívnánk a függvényt.
Feladat
