Dynamic programming (DP, dinamik dasturlaş) deb muammoni kiçik masalalarga ajratib, ularni faqat bir marta yeçiş va natijani keyingi bir xil tipdagi masalada işlatiş uçun saqlab turiş texnikasiga aytiladi. DP odatda rekursiya uçun optimizatsiya vazifasini ham bajaradi: agar rekursiv funksiya bitta berilgan qiymatni bir neça marta işlatayotgan bölsa (repeated calls), biz dynamic programming texnikasi bilan funksiyani optimallaştirişimiz mumkin. Şu oddiygina optimizatsiya işlaş vaqtini sezilarli darajada qisqartiradi.

Dynamic programminğni misol bilan tuşuntirişga harakat qilaman.

Fibonaççi sonlari haqida matematikaga qiziqqanlar bilişadi. Sonlar ketma-ketligida har bir son özidan avvalgi ikki sonning yiğindisiga teng:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

Uning formulasi: F_n = F_n-1 + F_n-2 , bunda F₀ = 0 va F₁ = 1

Hisoblaş uçun yoziladigan odatiy dastur quyidagiça körinişida böladi.

Grafik körinişida:

Kodning işlaş vaqti eksponental: O(N²).

E'tibor bersangiz, funksiya ikki marta çaqirilyapti va ikki holda ham deyarli bir xil hisoblaşni bajarmoqda. Biz hisoblaşni faqat bir marta amalga oşirib, keyingi safar saqlangan joydan öqib olişimiz mumkinmi?

Kodni optimizatsiya qilamiz (memoization varianti).

Natijalarni cache'ga yoziş bilan biz qaytariladigan hisoblaşlardan xalos böldik. Şu sababli dasturimizning işlaş vaqti eksponental vaqtdan linear vaqtgaça tuşdi.

Yuqoridagi kodning rekursiyasiz (tabulation) varianti:

Qanday qilib dasturda dynamic programming işlatiş mumkinligini aniqlaymiz?

Masalaning DPda yeçiş imkoni bor-yöqligini aniqlaş uçun uç savolga javob topiş kerak böladi.

1. Muammoni bir neça kiçik masalalarga böliş mumkinmi?
2. Muammoga rekursiv yeçimi bormi?
3. Kiçik masalalar qaytariluvçimi?

Agar uçala savolga ham javob "Ha" bölsa, u holda dynamic programminğni qöllaşning iloji bor.