In de informatica wordt gezegd dat een probleem overlappende deelproblemen heeft als het probleem kan worden opgesplitst in deelproblemen die meerdere keren worden hergebruikt of als een recursief algoritme voor het probleem hetzelfde deelprobleem steeds opnieuw oplost in plaats van steeds nieuwe te genereren subproblemen.
Wat zijn optimale onderbouw en overlappende deelproblemen bij dynamisch programmeren?
Een probleem heeft een optimale onderbouweigenschap als een optimale oplossing van het gegeven probleem kan worden verkregen door de optimale oplossing van zijn deelproblemen te gebruiken. Dynamic Programming maakt gebruik van deze eigenschap om een oplossing te vinden.
Wat is overlappend Subprobleem in dynamisch programmeren?
1) Overlappende subproblemen:
Dynamisch programmeren wordt voornamelijk gebruikt wanneer steeds weer oplossingen van dezelfde subproblemen nodig zijn. Bij dynamisch programmeren worden berekende oplossingen voor deelproblemen opgeslagen in een tabel, zodat deze niet opnieuw hoeven te worden berekend.
Wat is het verschil tussen optimale onderbouw en overlappende deelproblemen?
Ik begrijp de doelbenadering voor beide methoden waarbij Optimal Substructure de optimale oplossing berekent op basis van een invoer n, terwijl Overlappende subproblemen zich richten op alle oplossingen voor het invoerbereik, bijvoorbeeld van 1 tot n. Voor een probleem zoals het Rod Cutting Problem.
Welke van deze technieken gebruikt overlapping van deelproblemen?
Dynamisch programmeren is een techniek voor het oplossen van problemen met overlappende deelproblemen. Hierin slaan we het resultaat van het deelprobleem dat eenmalig is opgelost op voor toekomstig hergebruik. De techniek van het opslaan van subprobleemoplossingen wordt memoisatie genoemd.
