Dynamic Programming : Би нэг хэлсэн юмаа хоёр хэлдэггүй !

Энгүүнбаяр Ганзориг

• 2025-04-28
• algorithm, Coding, cp, dp, dynamic programming, Zeronith

Энэхүү нийтлэлийг уншиж буй таньд энэ өдрийг мэндийг хүргэе . Өнөөдөр бид Dynamic Programming-ийн талаар ярих болно . Тун сонирхолтой , чухал сэдэв тул та анхааралтай уншаарай . Dynamic Programming буюу DP нь маш том асуудлийг жижиг жижиг дэд асуудлуудад хуваан , тэрхүү дэд асуудлыг ганцхан удаа шийдээд тэрхүү хариугаа хадгалаад дахин дахин ашиглах аргачлал юм . Одоо энэ нийтлэлийн гарчигийг ойлгож байна уу ? . Энийг бид нар өрсөлдөөнт програмчлалын хүрээнд авч үзвэл “БИ НЭГ БОДСОН БОДЛОГОО ДАХИН БОДДОГГҮЙ” гэсэн утгатай юм шүү .

Dynamic Programming-ийн цөм нь :

Би яагаад энэхүү үйлдлийн хариуг хадгалаад дахин ашиглаж болох байхад байн байн тооцох ёстой юм бэ ? . Би ямар алтан загас уу ? (Ойлгоогүй хүмүүст : Алтан загас нь богино ой санамжтайгаар алдартай ) (Жич : Гэвч үнэндээ алтан загас нь хамгийн ой санамж муутай амьтан биш юм . Хайгаад судлаад үзээрэй . ) (Жичийн Жич : Зүгээр л хэлсийн)

Хэрвээ өөрийн тань бодох гэж байгаа бодлого :

• Нэг бодлогийг олон дахин бодоод байвал -> Наадах чинь яг DP
• Бодлогын дэд асуудлуудийг шийдсэнээр бодлогийг бодож байвал -> Наадах чинь бас л DP

Ямар үед DP ашиглах вэ ?

1. Overlapping Subproblems
   • Хэрвээ нэг асуудлаа дахин дахин шийдээд л байвал энэ бүр бат DP
     • Жишээ бодлого : Фибаночийн дараалал
       • Фибаночийн дараалал нь 0 1 1 2 3 5 8 13 21 …. . Ажиллах зарчим нь өмнөх 2 тооныхаа нийлбэрийг л авдаг . Энэхүү ганцхан зарчимийг тэр чигт нь ашигладаг шүү дээ . Одоо та харж чадаж байна уу ? . Энэхүү бодлого дээр яг нэг асуудлаа ганцхан зарчимаар дахин дахин ашиглаж байна
2. Optimal Substructure
   • Хэрвээ дэд асуудлуудаа хамгийн зөвөөр шийдээд тэр нь бодлогийг бодоход маш том нөлөө үзүүлж байвал тэр бас бат л DP (Гэхдээ энэны тухай яг доод талын хэсэгт нэмж ярих болно )
     • Жишээ бодлого : Хамгийн богино замийг ол
       • Та хоёр цэгийн хооронд хамгийн богино замыг олохдоо, тухайн замд орж буй бүх дэд замуудын хамгийн богино замыг олох хэрэгтэй. Та өөр өөр зам дээр боловч яг л нэг асуудал буюу аль нь хамгийн богино зам бэ гэх асуудлын шийдэж байгааг анзаарах хэрэгтэй .

Хэрвээ та миний өмнөх нийтлэл болох Greedy Algorithm-ийн талаарх нийтлэлийг уншсан бол Greedy Algorithm-аар бодогддог бодлогийн шинж чанар нь мөн адил Optimal Substructure гэсэн шинжийг агуулж байсан шүү дээ . Тэгвэл бидэнд маш том асуудал гараад ирлээ .

DP юм уу ? Greedy юм уу ?

DP болон Greedy 2-т 2 ууланд нь Optimal Substructure гэсэн шинж байсныг та анзаарсан байлгүй . Одоо үүнийг хэрхэн ялгах вэ гэдгийг таньд тайлбарлаж өгье .

• Greedy-ийн Optimal Substructure
  • Greedy нь тухайн нөхцөлд хамгийн зөв гэсэн ганцхан утгийг ашиглан цааш бодолт хийдэг билээ .
• DP-ийн Optimal Substructure
  • DP нь харин боломжит бүх утгийг хадгалдаг ба эдгээрийн ганц нь цааш хэрэглэгдэх байсан ч хамаагүй бүх утгийг хадгалдаг .

Тэгэхээр таньд хэрвээ тухайн нөхцөл байдалд ганц л шийдийг аван цааш үргэлжлүүлэн зөв шийдийг олох боломжтой хэмээн үзэж байвал Greedy .Харин надад яахын аргагүй бүх боломжит шийдүүд хэрэгтэй гэж үзвэл DP-г ашиглах нь ээ .

Dynamic Programming-ийн бодох аргачлалууд ?

Динамик програмчлалын аргачлал нь 2 хуваагддаг бөгөөд энэ нь

• Top to Down (Memoization)
  • Recursive-ээр асуудлийг шийддэг бөгөөд хийсэн тооцооллыг дахин тооцоолохоос сэргийлдэгээрээ давуу талтай .
• Bottom to Up (Tabulation)
  • Давталтаар шийддэг бөгөөд дэд асуудлуудыг шийдэн эцсийн хариуг үүсгэн гаргана .

ДҮГНЭЛТ :

Динамик программчлал (DP) нь давтагдах дэд асуудлуудтай, хамгийн сайн дэд шийдлүүдийг ашиглахад зориулагдсан техник юм. Энэ нь том асуудлыг жижиг дэд асуудлуудад хувааж, тэдгээрийн шийдлүүдийг хадгалан дахин ашиглахад оршдог. DP болон Greedy алгоритм хоорондоо ялгаатай бөгөөд DP бүх боломжит шийдлийг хадгалж, илүү нарийвчилсан шийдэл олдог бол Greedy зөвхөн хамгийн сайн нөхцлийг сонгодог. DP-г Memoization (Дээрээс доош) болон Tabulation (Доороос дээш) аргачлалаар хэрэглэх боломжтой гэдгийг энэхүү нийтлэлээр ойлгосон бизээ . Анхааралтай энэ хүртэл уншсан таньд баярлалаа . Тун удахгүй дараагийн нийтлэлээр уулзацгаая . Geronimoooo