В компютърните науки се казва, че проблемът има припокриващи се подпроблеми, ако проблемът може да бъде разделен на подпроблеми, които се използват повторно няколко пъти или рекурсивният алгоритъм за проблема решава един и същ подпроблем отново и отново, вместо винаги да генерира нови подпроблеми.
Какви са оптималната подструктура и припокриващите се подпроблеми в динамичното програмиране?
Проблемът има свойство на оптимална подструктура, ако може да се получи оптимално решение на дадения проблем чрез използване на оптималното решение на неговите подпроблеми. Динамичното програмиране се възползва от това свойство, за да намери решение.
Какво е припокриващ се подпроблем в динамичното програмиране?
1) Припокриващи се подпроблеми:
Динамичното програмиране е използва се главно, когато са необходими решения на едни и същи подпроблеми отново и отново. При динамичното програмиране изчислените решения на подпроблеми се съхраняват в таблица, така че да не се налага да се изчисляват повторно.
Каква е разликата между оптималната подструктура и припокриващите се подпроблеми?
Разбирам целевия подход и за двата метода, при които Оптималната подструктура изчислява оптималното решение въз основа на вход n, докато припокриващите се подпроблеми са насочени към всички решения за диапазона на вход, да речем от 1 до n. За проблем като проблема с рязане на прът.
Коя от тези техники използва припокриване на подпроблеми?
Динамичното програмиране е техника за решаване на проблеми с припокриващи се подпроблеми. В това съхраняваме резултата от подпроблема, който е решен веднъж за бъдеща повторна употреба. Техниката за съхраняване на решения на подпроблема се нарича запаметяване.
