Основи на динамичко програмирање


Ниво на тешкотија Лесно
Често прашувано во Infosys MAQ
Динамичко програмирање Теорија

Во основите на Динамичното програмирање, ќе ги покриеме основите на ДП и нејзините разлики од алчниот метод, Подели и освој и Рекурзија.

Динамичното програмирање е пристап исто како и повторување и поделба и освојување. Тој го дели проблемот на подпроблеми. Но, наместо да ги решава овие подпроблеми независно како поделба и победи и повторување, тој ги користи резултатите од претходните подпроблеми за слични пресметки познат и како преклопувачки проблем.

Се користи за оптимизација на програмите. Бидејќи ги користи претходно пресметаните резултати, користењето на неговата експоненцијална временска сложеност може да се сведе на полином. На пример - Временската сложеност на рекурзивното решение на Грди броеви е експоненцијална, а решението на ДП е линеарно.

Некои основни проблеми на ДП

  • Проблем со грди броеви
  • Промена на паричката
  • Броеви на Фибоначи
  • Проблем со броеви на ellвонче
  • Кула во Ханој
  • Броеви на ellвонче
  • Проблем со ранец

Динамичко програмирање (ДП) наспроти алчен метод

Во ДП, секој чекор го проценува решението со оглед на сегашните, како и претходните решенија за да се добие оптимално решение. Сепак, во алчниот алгоритам, ние ја избираме најдобрата опција со оглед на само моменталната ситуација.

Иако алчните методи се генерално побрзи од ДП и се исто така ефикасни во меморијата бидејќи не зачувуваат претходно пресметани вредности за идна употреба, тоа не дава сигурност за оптимално решение.

Динамичко програмирање (ДП) наспроти Подели и освој метод

Во поделба и освојување, ние делиме проблем на подпроблеми и го решаваме секој подпроблем независно. Сепак, во ДП наместо да решаваме проблеми независно, ние ги користиме претходно добиените резултати за нови пресметки. Со други зборови, можеме да кажеме Подели и освои + Мемоизација = динамичен пристап од горе надолу.

(Мемоизацијата се однесува на техниката на зачувување на претходно пресметаните резултати генерално во хаш-мапа за да се спречат пресметките на истите проблеми одново и одново.)

Динамичко програмирање (ДП) наспроти методот на рекурзија

ДП ги зачувува претходно пресметаните решенија за да ги користите како и кога е потребно повторно во иднина за да избегнете повторно пресметки. Меѓутоа, при повторување, постои можност за повторни пресметки, што е непотребно, бидејќи не складира вредности.

Рекурзијата доведува до повторна пресметка на проблемите неколку пати, затоа во вакви случаи временската сложеност на повторувањето е секогаш поголема од решението за ДП.

Во оваа статија, опфативме околу Динамичко програмирање основни работи. Во следните написи, ќе покриеме неколку основни проблеми на ДП.

Суд Прашања за интервју