V informatike sa o probléme hovorí, že má prekrývajúce sa podproblémy, ak je možné problém rozdeliť na podproblémy, ktoré sa niekoľkokrát použijú, alebo rekurzívny algoritmus problému rieši stále ten istý podproblém namiesto toho, aby vždy generoval nové podproblémy.
Aké sú optimálne podštruktúry a prekrývajúce sa podproblémy v dynamickom programovaní?
Problém má vlastnosť optimálnej subštruktúry, ak sa optimálne riešenie daného problému dá dosiahnuť použitím optimálneho riešenia jeho podproblémov. Dynamické programovanie využíva túto vlastnosť na nájdenie riešenia.
Čo je prekrývajúci sa podproblém v dynamickom programovaní?
1) Prekrývajúce sa podproblémy:
Dynamické programovanie sa používa hlavne vtedy, keď je potrebné znova a znova riešiť rovnaké podproblémy. V dynamickom programovaní sa vypočítané riešenia čiastkových problémov ukladajú do tabuľky, takže ich nie je potrebné prepočítavať.
Aký je rozdiel medzi optimálnou podštruktúrou a prekrývajúcimi sa podproblémami?
Rozumiem cieľovému prístupu pre obe metódy, kde Optimal Substructure vypočítava optimálne riešenie na základe vstupu n, zatiaľ čo Overlapping Subproblems sa zameriava na všetky riešenia pre rozsah vstupu, povedzme od 1 do n. Pre problém, ako je problém s rezaním tyče.
Ktorá z týchto techník využíva prekrývanie čiastkových problémov?
Dynamické programovanie je technika na riešenie problémov s prekrývajúcimi sa podproblémami. V tomto ukladáme výsledok čiastkového problému, ktorý je raz vyriešený, pre budúce opätovné použitie. Technika ukladania riešení čiastkových problémov sa nazýva memoizácia.
