Динамикалык программалоонун негиздери


Кыйынчылык деңгээли жеңил
Көп суралган Infosys MAQ
Динамикалык программалоо теория

Динамикалык программалоонун негиздеринде биз DP негиздерин жана анын ач көздүк методунан, Divide and Conquer жана Recursionдон айырмачылыктарын камтыйбыз.

Динамикалык программалоо - бул рекурсия жана бөлүү жана багындыруу сыяктуу ыкма. Бул көйгөйдү чакан проблемаларга бөлөт. Бөлүү, багындыруу жана рекурсия сыяктуу бул субпроблемаларды өз алдынча чечүүнүн ордуна, мурунку подпроблемалардын натыйжаларын окшош эсептөөлөр үчүн колдонот, ошондой эле бири-бири менен кайчылашкан маселе.

Ал программаларды оптималдаштыруу үчүн колдонулат. Мурда эсептелген натыйжаларды колдонуп жаткандыктан, анын экспоненциалдуу убакыт татаалдыгын колдонуп, көп мүчөгө жеткирүүгө болот. Мисалы - Чиркин Сандардын рекурсивдүү чечиминин убакыт татаалдыгы экспоненциалдуу, ал эми DP чечими сызыктуу.

DP айрым негизги көйгөйлөрү

  • Чиркин сандар көйгөйү
  • Монета алмаштыруу
  • Фибоначчи сандары
  • Коңгуроо номерлери көйгөйү
  • Ханой мунарасынын
  • Коңгуроо номерлери
  • Рюкзак көйгөйү

Dynamic Programming (DP) vs Greedy Method

DPде ар бир кадам оптималдуу чечим алуу үчүн учурдагы жана мурунку чечимдерди эске алуу менен чечимге баа берет. Бирок, ач көз алгоритмде биз учурдагы кырдаалды гана эске алып, мыкты вариантты тандайбыз.

Ачкөз методдор көбүнчө DPге караганда ылдамыраак жана эс тутумда натыйжалуу болгону менен, келечекте колдонуу үчүн мурда эсептелген баалуулуктарды сактабайт, бирок бул оптималдуу чечимге ишендирбейт.

Динамикалык программалоо (DP) vs Divide & Conquer Method

Бөлүү жана жеңүү менен биз көйгөйдү чакан көйгөйлөргө бөлүп, ар бир чакан көйгөйдү өз алдынча чечебиз. Бирок, DPде көйгөйлөрдү өз алдынча чечүүдөн көрө, мурун алынган натыйжаларды жаңы эсептөөлөр үчүн колдонобуз. Башка сөз менен айтканда, биз Бөл жана жеңип ал + Эске тутуу = жогортон ылдый динамикалык мамиле деп айта алабыз.

(Эске тутуу, мурунку эсептелген натыйжаларды жалпысынан хэш-картада сактоо, ошол эле көйгөйлөрдү кайра-кайра эсептөөгө жол бербөө техникасын билдирет.)

Динамикалык программалоо (DP) vs рекурсия ыкмасы

DP аларды эсептөө үчүн алдын-ала эсептелген чечимдерди сактайт жана келечекте дагы бир жолу эсептеп чыкпоо үчүн талап кылынат. Бирок, рекурсияда, баалуулуктарды сактабагандыктан, ашыкча эсептөөлөрдү жүргүзүү мүмкүнчүлүгү бар.

Рекурсия көйгөйлөрдү бир нече жолу кайра эсептөөгө алып келет, андыктан мындай учурларда рекурсиянын убакыт татаалдыгы DP чечимине караганда көбүрөөк болот.

Бул макалада биз жөнүндө камтылган Динамикалык программалоо негиздери. Кийинки макалаларда DP боюнча айрым негизги көйгөйлөрдү талкуулайбыз.

шилтеме Интервью суроолору