Dynamic programming — muammoni o‘zaro takrorlanadigan kichik subproblemlarga ajratib, ularning natijasini bir marta hisoblab saqlash orqali yechish usulidir. U optimal substructure va overlapping subproblems xususiyatlari mavjud bo‘lganda samarali. Atamadagi “programming” dastur yozishdan ko‘ra rejalashtirish ma’nosiga yaqin.
Asosiy g‘oya
Naive recursion bir xil subproblemni ko‘p marta qayta hisoblaydi. Fibonacci misolida F(n) uchun F(n-1) va F(n-2) chaqiriladi, ularning daraxtida ko‘p tugun takrorlanadi. Natijani jadvalga saqlash hisoblash sonini keskin kamaytiradi.
State subproblemni to‘liq aniqlaydigan parametrlar to‘plamidir. Transition katta state javobini kichik state javoblaridan hosil qiladi. Base case rekursiya yoki jadvalning boshlang‘ich qiymatini belgilaydi.
Memoization
Top-down usul odatiy recursive yechimga cache qo‘shadi. Funksiya state keyini tekshiradi; natija mavjud bo‘lsa qaytaradi, bo‘lmasa hisoblab saqlaydi. Faqat haqiqatan kerak bo‘lgan state’lar hisoblanadi.
Memoization recursion stack va hash map overheadiga ega bo‘lishi mumkin. State key immutable va equality aniq bo‘lishi kerak. Global cache turli input yoki configuration natijalarini aralashtirmasligi uchun kontekst keyga kiradi.
Tabulation
Bottom-up usul base case’dan boshlab jadvalni dependency tartibida to‘ldiradi. Recursive stack yo‘q va array access tez bo‘lishi mumkin. Biroq barcha state’lar kerak bo‘lmasa ortiqcha ish bajariladi.
Iteration tartibi transition talab qilgan oldingi qiymatlar allaqachon tayyor bo‘lishini ta’minlaydi. DAG uchun topological order, interval DP uchun uzunlik bo‘yicha, grid uchun qator yoki ustun bo‘yicha yurish mumkin.
Yechimni tiklash
Faqat optimal qiymat emas, tanlangan elementlar kerak bo‘lsa parent yoki choice jadvali saqlanadi. Final state’dan orqaga yurib yo‘l tiklanadi. Xotirani kamaytirib faqat ikki qator saqlansa, to‘liq yechimni tiklash uchun qayta hisoblash yoki alohida compact choice kerak bo‘lishi mumkin.
Masalan, shortest path, knapsack, edit distance, sequence alignment va matrix-chain multiplication dynamic programming bilan yechilishi mumkin. Har birida state va transition boshqacha; tayyor formula ko‘r-ko‘rona ko‘chirilmaydi.
Murakkablik
Vaqt taxminan state soni bilan har state’dagi transition narxining ko‘paytmasi. Space jadvaldagi state soniga bog‘liq. Rolling array faqat oldingi qatlam kerak bo‘lsa space’ni O(n²)dan O(n)ga kamaytirishi mumkin.
State dimension ortishi curse of dimensionality keltiradi. Constraint, symmetry, pruning yoki sparse map faqat reachable state’larni saqlaydi. Pseudo-polynomial algoritm son qiymatiga polynomial, uning bit uzunligiga esa exponential bo‘lishi mumkin; knapsack capacity bunga misol.
To‘g‘rilik
Optimal substructure isbotida optimal yechim ichidagi subyechim ham tegishli subproblem uchun optimal ekani ko‘rsatiladi. Transition barcha qonuniy oxirgi qarorlarni qamrab oladi. Induction jadval tartibi bo‘yicha har state to‘g‘ri hisoblanganini isbotlaydi.
State compression
State’da kelajak qaroriga ta’sir qilmaydigan tarix saqlansa jadval keragidan katta bo‘ladi. Yetarli statistikani topib state dimensionni kamaytirish DP dizaynining asosiy qismidir. Bitmask DP kichik elementlar to‘plamini integer bitlari bilan ifodalaydi, lekin state soni 2^n bo‘lib qoladi. Monotonic queue, prefix minimum yoki convex hull trick ayrim transitionni barcha oldingi state’larni ko‘rishdan tezlashtiradi. Bunday optimallashtirishdan oldin transitionning monotonic yoki algebraik sharti isbotlanadi; aks holda ayrim inputda noto‘g‘ri natija beradi.
DP jadvalidagi unreachable state uchun infinity sentinel tanlanganda unga son qo‘shish integer overflow bermasligi kerak; transition avval state mavjudligini tekshiradi.
Bog‘liq tushunchalar
Memoization, Tabulation, Optimal substructure, Recursion, Knapsack problem, State space