rust_algorithms/dp/mod.rs
1//! # Dinamik dasturlash (Dynamic Programming)
2//!
3//! Darslik: `10-dynamic-programming/`
4//!
5//! **DP bir jumlada:** bir xil kichik masalani ikki marta yechmang — javobini
6//! yozib qo'ying va keyingi safar tayyorini oling.
7//!
8//! ## DP qachon ishlaydi? (ikki shart)
9//!
10//! 1. **Optimal substructure** — katta masalaning yechimi kichiklarining yechimidan
11//! quriladi (`fib(n) = fib(n-1) + fib(n-2)`);
12//! 2. **Overlapping subproblems** — bir xil kichik masala qayta-qayta uchraydi.
13//!
14//! Faqat 1-shart bo'lsa — bu "bo'l va hukmronlik qil" (merge sort), DP emas.
15//!
16//! ## Ikki uslub
17//!
18//! | | Top-down (memoizatsiya) | Bottom-up (tabulyatsiya) |
19//! |---|---|---|
20//! | Ko'rinishi | Rekursiya + kesh | Tsikl + jadval |
21//! | Yozish | Osonroq (tabiiy fikrlash) | Biroz qiyinroq |
22//! | Tezlik | Rekursiya qo'shimcha xarajati bor | Tezroq |
23//! | Xotira | Stack + kesh | Faqat jadval (ko'pincha siqish mumkin) |
24//!
25//! ## DP masalasini yechish tartibi (5 qadam)
26//!
27//! ```text
28//! 1. HOLAT (state): dp[i] nimani anglatadi? — eng muhim qadam!
29//! 2. O'TISH (recurrence): dp[i] ni kichikroqlardan qanday olamiz?
30//! 3. BOSHLANG'ICH: eng kichik holat(lar) qiymati
31//! 4. TARTIB: qaysi tartibda to'ldiramiz?
32//! 5. JAVOB: jadvalning qayerida turadi?
33//! ```
34//!
35//! ## Modulda nima bor
36//!
37//! | Funksiya | Klassik nomi | Time | Space |
38//! |---|---|---|---|
39//! | [`fib_memo`] / [`fib_tab`] | Fibonachchi | O(n) | O(n) / O(1) |
40//! | [`knapsack_01`] | 0/1 xalta | O(n·W) | O(W) |
41//! | [`lcs`] | Eng uzun umumiy ketma-ketlik | O(n·m) | O(n·m) |
42//! | [`lis`] | Eng uzun o'suvchi ketma-ketlik | O(n log n) | O(n) |
43//! | [`edit_distance`] | Levenshtein masofasi | O(n·m) | O(m) |
44//! | [`coin_change_min`] | Qaytim (optimal) | O(n·summa) | O(summa) |
45//! | [`max_subarray`] | Kadane | O(n) | O(1) |
46//! | [`unique_paths`] | Panjarada yo'llar | O(n·m) | O(m) |
47
48mod classic;
49mod sequences;
50
51pub use classic::{
52 coin_change_min, fib_memo, fib_tab, knapsack_01, knapsack_01_items, unique_paths,
53};
54pub use sequences::{edit_distance, lcs, lcs_len, lis, lis_len, max_subarray};