Néhány szakkörön dinamikus programozással megoldható feladatokat fogunk gyakorolni. 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.
- Sok esetben tovább gyorsítható a megoldás, ha a rekurzív hívások valamilyen nyilvánvaló sorrendben történnek (például mindig eggyel kisebb paraméter értékkel). Ilyenkor egy egyszerű ciklussal is feltölthető az a tömb, ami a már kiszámított értékeket tárolja.
Akkor tudjuk a rekurzió lényegesen gyorsítani ezzel a módszerrel, ha sok átfedő részfeladat van, vagyis a "buta" rekurzió sokszor futna rá ugyanazon részprobléma kiszámítására.
Feladatok3N+1 probléma Kincsvadász A fáraó lépcsője
|