U informatici se kaže da problem ima podprobleme koji se preklapaju ako se problem može rastaviti na podprobleme koji se koriste nekoliko puta ili rekurzivni algoritam za problem rješava isti podproblem iznova i iznova umjesto da uvijek generira nove podproblemi.
Što su optimalna podstruktura i podproblemi preklapanja u dinamičkom programiranju?
Problem ima svojstvo optimalne podstrukture ako se optimalno rješenje zadanog problema može dobiti korištenjem optimalnog rješenja njegovih podproblema. Dinamičko programiranje iskorištava prednosti ovog svojstva da pronađe rješenje.
Što je podproblem preklapanja u dinamičkom programiranju?
1) Preklapajući podproblemi:
Dinamičko programiranje uglavnom se koristi kada su rješenja istih podproblema potrebna uvijek iznova. U dinamičkom programiranju, izračunata rješenja podproblema pohranjuju se u tablicu tako da se ne moraju ponovno izračunavati.
Koja je razlika između optimalne podstrukture i podproblema koji se preklapaju?
Razumijem ciljni pristup za obje metode gdje Optimalna podstruktura izračunava optimalno rješenje na temelju ulaza n, dok Preklapajući podproblemi ciljaju sva rješenja za raspon ulaza, recimo od 1 do n. Za problem kao što je problem rezanja šipke.
Koja od ovih tehnika koristi preklapanje podproblema?
Dinamičko programiranje je tehnika za rješavanje problema s podproblemima koji se preklapaju. U to pohranjujemo rezultat podproblema koji je jednom riješen za buduću ponovnu upotrebu. Tehnika pohranjivanja rješenja podproblema naziva se memoizacija.
