Module dp 

Dinamik dasturlash (Dynamic Programming)

Darslik: 10-dynamic-programming/

DP bir jumlada: bir xil kichik masalani ikki marta yechmang — javobini yozib qo’ying va keyingi safar tayyorini oling.

DP qachon ishlaydi? (ikki shart)

1. Optimal substructure — katta masalaning yechimi kichiklarining yechimidan quriladi (fib(n) = fib(n-1) + fib(n-2));
2. Overlapping subproblems — bir xil kichik masala qayta-qayta uchraydi.

Faqat 1-shart bo’lsa — bu “bo’l va hukmronlik qil” (merge sort), DP emas.

Ikki uslub

	Top-down (memoizatsiya)	Bottom-up (tabulyatsiya)
Ko’rinishi	Rekursiya + kesh	Tsikl + jadval
Yozish	Osonroq (tabiiy fikrlash)	Biroz qiyinroq
Tezlik	Rekursiya qo’shimcha xarajati bor	Tezroq
Xotira	Stack + kesh	Faqat jadval (ko’pincha siqish mumkin)

DP masalasini yechish tartibi (5 qadam)

1. HOLAT (state):     dp[i] nimani anglatadi? — eng muhim qadam!
2. O'TISH (recurrence): dp[i] ni kichikroqlardan qanday olamiz?
3. BOSHLANG'ICH:      eng kichik holat(lar) qiymati
4. TARTIB:            qaysi tartibda to'ldiramiz?
5. JAVOB:             jadvalning qayerida turadi?

Modulda nima bor

Funksiya	Klassik nomi	Time	Space
fib_memo / fib_tab	Fibonachchi	O(n)	O(n) / O(1)
knapsack_01	0/1 xalta	O(n·W)	O(W)
lcs	Eng uzun umumiy ketma-ketlik	O(n·m)	O(n·m)
lis	Eng uzun o’suvchi ketma-ketlik	O(n log n)	O(n)
edit_distance	Levenshtein masofasi	O(n·m)	O(m)
coin_change_min	Qaytim (optimal)	O(n·summa)	O(summa)
max_subarray	Kadane	O(n)	O(1)
unique_paths	Panjarada yo’llar	O(n·m)	O(m)

Functions

coin_change_min

Qaytim berish — optimal yechim (DP), ochko’z yondashuvdan farqli.

edit_distance

Levenshtein masofasi — bir satrni ikkinchisiga aylantirish uchun kerak bo’lgan minimal amallar soni (qo’shish, o’chirish, almashtirish).

fib_memo

Fibonachchi — top-down (memoizatsiya) uslubi.

fib_tab

Fibonachchi — bottom-up (tabulyatsiya) + xotirani siqish.

knapsack_01

0/1 xalta masalasi — buyumni yo butun olamiz, yo umuman olmaymiz.

knapsack_01_items

0/1 xalta + qaysi buyumlar tanlanganini qaytaradi.

lcs

LCS ning o’zini (satr sifatida) qaytaradi.

lcs_len

LCS — eng uzun umumiy ketma-ketlik uzunligi (Longest Common Subsequence).

lis

LIS ning o’zini qaytaradi (O(n log n), ota indekslarini saqlab).

lis_len

LIS — eng uzun qat’iy o’suvchi ketma-ketlik uzunligi, O(n log n) da.

max_subarray

Kadane algoritmi — eng katta yig’indili qism-massiv (maximum subarray).

unique_paths

Panjarada yo’llar soni: rows × cols to’rning chap-yuqori burchagidan o’ng-pastki burchagiga faqat o’ngga va pastga yurib nechta yo’l bor?