U informatici se kaže da problem ima podprobleme koji se preklapaju ako se problem može podijeliti na podprobleme koji se koriste nekoliko puta ili rekurzivni algoritam za problem rješava isti podproblem iznova i iznova umjesto da uvijek generiše nove podproblemi.
Šta su optimalna podstruktura i podproblemi preklapanja u dinamičkom programiranju?
Problem ima svojstvo optimalne podstrukture ako se optimalno rješenje datog problema može dobiti korištenjem optimalnog rješenja njegovih podproblema. Dinamičko programiranje koristi prednosti ove osobine da pronađe rješenje.
Šta je podproblem preklapanja u dinamičkom programiranju?
1) Preklapajući podproblemi:
Dinamičko programiranje se uglavnom koristi kada su rješenja istih podproblema potrebna uvijek iznova. U dinamičkom programiranju, izračunata rješenja podproblema se pohranjuju u tablicu tako da se ne moraju ponovo 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 osnovu ulaza n, dok Preklapajući podproblemi ciljaju sva rješenja za raspon unosa, 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 sa podproblemima koji se preklapaju. U ovo pohranjujemo rezultat podproblema koji je jednom riješen za buduću ponovnu upotrebu. Tehnika pohranjivanja rješenja podproblema naziva se memoizacija.
