Асновы дынамічнага праграмавання  


Узровень складанасці Лёгка
Часта пытаюцца ў Infosys MAQ
Дынамічнае праграмаванне тэорыя

У асновах дынамічнага праграмавання мы разгледзім асновы ДП і яе адрозненні ад прагнага метаду "Падзялі і ўладай" і "Рэкурсія".

Дынамічнае праграмаванне - гэта падыход, падобны да рэкурсіі і падзелу і заваёвы. Ён падзяляе праблему на падзадачы. Але замест таго, каб вырашаць гэтыя падзадачы самастойна, як падзяліць і перамагчы і рэкурсія, ён выкарыстоўвае вынікі папярэдніх падзадач для аналагічных вылічэнняў, таксама вядомых як праблема перакрыцця.

Ён выкарыстоўваецца для аптымізацыі праграм. Паколькі ён выкарыстоўвае вылічаныя раней вынікі, выкарыстанне яго экспанентнай часавай складанасці можа быць зведзена да мнагачлена. Напрыклад - часовая складанасць рэкурсіўнага вырашэння брыдкіх лікаў экспанентная, а рашэння DP лінейная.

Некаторыя асноўныя праблемы ДП  

  • Непрыгожая праблема з лічбамі
  • Змена манет
  • Лікі Фібаначы
  • Праблема з званкамі
  • вежа Ханоя
  • Лічбы званочка
  • Праблема з заплечнікам

Дынамічнае праграмаванне (DP) супраць прагнага метаду  

У DP кожны крок ацэньвае рашэнне з улікам бягучага, а таксама папярэдніх рашэнняў, каб атрымаць аптымальнае рашэнне. Аднак у прагным алгарытме мы выбіраем лепшы варыянт, улічваючы толькі бягучую сітуацыю.

Хоць прагныя метады, як правіла, хутчэйшыя, чым DP, а таксама эфектыўныя для памяці, паколькі не захоўваюць вылічаныя раней значэнні для будучага выкарыстання, гэта не дае гарантыі аптымальнага рашэння.

Глядзіце таксама
Рэалізаваць стэк, выкарыстоўваючы адзіную чаргу

Дынамічнае праграмаванне (DP) супраць метаду Divide & Conquer  

У падзеле і заваяванні мы падзяляем задачу на падзадачы і вырашаем кожную падзадачу самастойна. Аднак у DP замест таго, каб вырашаць праблемы самастойна, мы выкарыстоўваем атрыманыя раней вынікі для новых вылічэнняў. Іншымі словамі, мы можам сказаць Divide and Conquer + Memoization = дынамічны падыход зверху ўніз.

(Мемаізацыя адносіцца да тэхнікі захоўвання раней вылічаных вынікаў, як правіла, у хэш-карце, каб прадухіліць вылічэнні адных і тых жа праблем зноў і зноў.)

Дынамічнае праграмаванне (DP) супраць метаду рэкурсіі  

DP захоўвае вылічаныя раней рашэнні, каб выкарыстоўваць іх па меры неабходнасці ў будучыні, каб пазбегнуць паўторных вылічэнняў. Аднак у рэкурсіі існуе магчымасць паўторных вылічэнняў, што непатрэбна, бо яно не захоўвае значэнні.

Рэкурсія вядзе да пераразліку задач некалькі разоў, таму ў такіх выпадках складанасць рэкурсіі заўсёды больш, чым рашэнне DP.

У гэтым артыкуле мы распавялі пра Дынамічнае праграмаванне асновы. У наступных артыкулах мы разгледзім некаторыя асноўныя праблемы, звязаныя з ДП.

Спасылка Інтэрв'ю Пытанні