rust_algorithms/dp/classic.rs
1//! Klassik DP masalalari: Fibonachchi, xalta, qaytim, panjarada yo'llar.
2
3use std::collections::HashMap;
4
5/// Fibonachchi — **top-down** (memoizatsiya) uslubi.
6///
7/// Sodda rekursiya `fib(n-1) + fib(n-2)` bir xil qiymatni eksponensial marta
8/// hisoblaydi: `fib(40)` uchun ~2 milliard chaqiruv. Kesh qo'shsak — `n` ta chaqiruv.
9///
10/// ```text
11/// Keshsiz: fib(5)
12/// / \
13/// fib(4) fib(3) ← fib(3) ikki marta hisoblanadi
14/// / \ / \
15/// fib(3) fib(2) ...
16///
17/// Kesh bilan: har bir fib(k) atigi bir marta hisoblanadi.
18/// ```
19///
20/// - **Time:** O(n), **Space:** O(n) (kesh + stack).
21///
22/// # Misol
23/// ```
24/// use rust_algorithms::dp::fib_memo;
25///
26/// assert_eq!(fib_memo(10), 55);
27/// assert_eq!(fib_memo(50), 12586269025); // bir zumda
28/// ```
29pub fn fib_memo(n: u32) -> u128 {
30 fn go(n: u32, kesh: &mut HashMap<u32, u128>) -> u128 {
31 if n < 2 {
32 return n as u128;
33 }
34 if let Some(&v) = kesh.get(&n) {
35 return v; // tayyor javob
36 }
37 let v = go(n - 1, kesh) + go(n - 2, kesh);
38 kesh.insert(n, v);
39 v
40 }
41 go(n, &mut HashMap::new())
42}
43
44/// Fibonachchi — **bottom-up** (tabulyatsiya) + xotirani siqish.
45///
46/// `dp[i] = dp[i-1] + dp[i-2]` — bizga faqat oxirgi ikkita qiymat kerak,
47/// demak butun jadvalni saqlash shart emas: **O(1) xotira**.
48///
49/// # Misol
50/// ```
51/// use rust_algorithms::dp::{fib_memo, fib_tab};
52///
53/// assert_eq!(fib_tab(90), fib_memo(90));
54/// assert_eq!(fib_tab(0), 0);
55/// ```
56pub fn fib_tab(n: u32) -> u128 {
57 let (mut a, mut b) = (0u128, 1u128);
58 for _ in 0..n {
59 let t = a + b;
60 a = b;
61 b = t;
62 }
63 a
64}
65
66/// **0/1 xalta masalasi** — buyumni yo butun olamiz, yo umuman olmaymiz.
67///
68/// **Holat:** `dp[w]` = sig'imi `w` bo'lgan xaltaga joylash mumkin bo'lgan maksimal qiymat.
69///
70/// **O'tish:** har bir buyum uchun `dp[w] = max(dp[w], dp[w - og'irlik] + qiymat)`.
71///
72/// **Muhim nozik nuqta:** sig'im bo'yicha **teskari** (kattadan kichikka) yuramiz —
73/// aks holda bitta buyumni bir necha marta olib qo'yamiz (u holda bu boshqa masala:
74/// "cheksiz xalta").
75///
76/// - **Time:** O(n·W), **Space:** O(W) — 2D jadvalni 1D ga siqdik.
77///
78/// > Bu **pseudo-polinomial** murakkablik: `W` kirish hajmi emas, kirish *qiymati*.
79/// > `W` juda katta bo'lsa (masalan, 10⁹) bu usul ishlamaydi.
80///
81/// # Misol
82/// ```
83/// use rust_algorithms::dp::knapsack_01;
84///
85/// let ogirliklar = [1, 3, 4, 5];
86/// let qiymatlar = [1, 4, 5, 7];
87/// assert_eq!(knapsack_01(&ogirliklar, &qiymatlar, 7), 9); // 3 + 4 → 4 + 5
88///
89/// // Ochko'zlik bu yerda xato qiladi: eng "zich" buyum (5/4=1.25) ni olsa 7+1=8 chiqadi
90/// ```
91pub fn knapsack_01(weights: &[usize], values: &[i64], capacity: usize) -> i64 {
92 assert_eq!(weights.len(), values.len());
93 let mut dp = vec![0i64; capacity + 1];
94
95 for (&w, &v) in weights.iter().zip(values.iter()) {
96 if w > capacity {
97 continue;
98 }
99 for sigim in (w..=capacity).rev() {
100 dp[sigim] = dp[sigim].max(dp[sigim - w] + v);
101 }
102 }
103 dp[capacity]
104}
105
106/// 0/1 xalta + **qaysi buyumlar** tanlanganini qaytaradi.
107///
108/// Buning uchun to'liq 2D jadval kerak (O(n·W) xotira), chunki orqaga qarab
109/// yurib tanlovni tiklaymiz.
110///
111/// Qaytadi: `(maksimal_qiymat, tanlangan_buyum_indekslari)`.
112///
113/// # Misol
114/// ```
115/// use rust_algorithms::dp::knapsack_01_items;
116///
117/// let (qiymat, buyumlar) = knapsack_01_items(&[1, 3, 4, 5], &[1, 4, 5, 7], 7);
118/// assert_eq!(qiymat, 9);
119/// assert_eq!(buyumlar, vec![1, 2]); // og'irliklari 3 va 4
120/// ```
121pub fn knapsack_01_items(weights: &[usize], values: &[i64], capacity: usize) -> (i64, Vec<usize>) {
122 let n = weights.len();
123 let mut dp = vec![vec![0i64; capacity + 1]; n + 1];
124
125 for i in 1..=n {
126 for w in 0..=capacity {
127 dp[i][w] = dp[i - 1][w]; // buyumni olmaymiz
128 if weights[i - 1] <= w {
129 dp[i][w] = dp[i][w].max(dp[i - 1][w - weights[i - 1]] + values[i - 1]);
130 }
131 }
132 }
133
134 // Orqaga yurib, qaysi buyumlar olinganini aniqlaymiz
135 let mut tanlangan = Vec::new();
136 let mut w = capacity;
137 for i in (1..=n).rev() {
138 if dp[i][w] != dp[i - 1][w] {
139 tanlangan.push(i - 1);
140 w -= weights[i - 1];
141 }
142 }
143 tanlangan.reverse();
144 (dp[n][capacity], tanlangan)
145}
146
147/// Qaytim berish — **optimal** yechim (DP), ochko'z yondashuvdan farqli.
148///
149/// **Holat:** `dp[s]` = `s` summani yig'ish uchun kerak bo'lgan minimal tangalar soni.
150/// **O'tish:** `dp[s] = 1 + min(dp[s - tanga])` barcha tangalar bo'yicha.
151///
152/// - **Time:** O(tangalar × summa), **Space:** O(summa).
153///
154/// # Misol
155/// ```
156/// use rust_algorithms::dp::coin_change_min;
157/// use rust_algorithms::greedy::coin_change_greedy;
158///
159/// // Ochko'zlik xato qiladigan holat:
160/// assert_eq!(coin_change_min(&[1, 3, 4], 6), Some(2)); // 3 + 3
161/// assert_eq!(coin_change_greedy(&[1, 3, 4], 6).unwrap().len(), 3); // 4 + 1 + 1
162///
163/// assert_eq!(coin_change_min(&[2], 3), None);
164/// assert_eq!(coin_change_min(&[1, 5, 10], 0), Some(0));
165/// ```
166pub fn coin_change_min(coins: &[u64], amount: u64) -> Option<usize> {
167 let amount = amount as usize;
168 let mut dp = vec![usize::MAX; amount + 1];
169 dp[0] = 0;
170
171 for s in 1..=amount {
172 for &c in coins {
173 let c = c as usize;
174 if c == 0 || c > s {
175 continue;
176 }
177 if dp[s - c] != usize::MAX {
178 dp[s] = dp[s].min(dp[s - c] + 1);
179 }
180 }
181 }
182 if dp[amount] == usize::MAX {
183 None
184 } else {
185 Some(dp[amount])
186 }
187}
188
189/// Panjarada yo'llar soni: `rows × cols` to'rning chap-yuqori burchagidan
190/// o'ng-pastki burchagiga faqat **o'ngga** va **pastga** yurib nechta yo'l bor?
191///
192/// **Holat:** `dp[j]` = joriy qatordagi `j` -katakka nechta yo'l bor.
193/// **O'tish:** `dp[j] += dp[j-1]` (yuqoridan + chapdan).
194///
195/// - **Time:** O(rows·cols), **Space:** O(cols).
196///
197/// # Misol
198/// ```
199/// use rust_algorithms::dp::unique_paths;
200///
201/// assert_eq!(unique_paths(3, 3), 6);
202/// assert_eq!(unique_paths(1, 10), 1);
203/// assert_eq!(unique_paths(0, 5), 0);
204/// ```
205pub fn unique_paths(rows: usize, cols: usize) -> u64 {
206 if rows == 0 || cols == 0 {
207 return 0;
208 }
209 let mut dp = vec![1u64; cols];
210 for _ in 1..rows {
211 for j in 1..cols {
212 dp[j] += dp[j - 1];
213 }
214 }
215 dp[cols - 1]
216}
217
218#[cfg(test)]
219mod tests {
220 use super::*;
221 use crate::util::Rng;
222
223 #[test]
224 fn fibonachchi_ikki_uslub_mos() {
225 for n in 0..=100 {
226 assert_eq!(fib_memo(n), fib_tab(n), "n = {n}");
227 }
228 }
229
230 #[test]
231 fn xalta_klassik() {
232 assert_eq!(knapsack_01(&[1, 3, 4, 5], &[1, 4, 5, 7], 7), 9);
233 assert_eq!(knapsack_01(&[10, 20, 30], &[60, 100, 120], 50), 220);
234 assert_eq!(knapsack_01(&[], &[], 10), 0);
235 assert_eq!(knapsack_01(&[100], &[1000], 10), 0); // sig'maydi
236 }
237
238 #[test]
239 fn xalta_buyumlar_mos() {
240 let mut rng = Rng::new(707);
241 for _ in 0..30 {
242 let n = 8;
243 let w: Vec<usize> = (0..n).map(|_| rng.below(10) + 1).collect();
244 let v: Vec<i64> = (0..n).map(|_| rng.range(1, 30)).collect();
245 let cap = 20;
246
247 let faqat_qiymat = knapsack_01(&w, &v, cap);
248 let (qiymat, buyumlar) = knapsack_01_items(&w, &v, cap);
249 assert_eq!(faqat_qiymat, qiymat);
250
251 let jami_ogirlik: usize = buyumlar.iter().map(|&i| w[i]).sum();
252 let jami_qiymat: i64 = buyumlar.iter().map(|&i| v[i]).sum();
253 assert!(jami_ogirlik <= cap);
254 assert_eq!(jami_qiymat, qiymat);
255 }
256 }
257
258 #[test]
259 fn qaytim_dp_ochkozdan_yaxshi_yoki_teng() {
260 let tangalar = [1u64, 3, 4];
261 for summa in 1u64..60 {
262 let dp = coin_change_min(&tangalar, summa).unwrap();
263 let greedy = crate::greedy::coin_change_greedy(&tangalar, summa)
264 .unwrap()
265 .len();
266 assert!(dp <= greedy, "summa = {summa}");
267 }
268 }
269
270 #[test]
271 fn qaytim_chegaraviy_holatlar() {
272 assert_eq!(coin_change_min(&[], 0), Some(0));
273 assert_eq!(coin_change_min(&[], 5), None);
274 assert_eq!(coin_change_min(&[0, 1], 3), Some(3));
275 }
276
277 #[test]
278 fn panjaradagi_yollar() {
279 assert_eq!(unique_paths(2, 2), 2);
280 assert_eq!(unique_paths(3, 7), 28);
281 // C(rows+cols-2, rows-1) formulasi bilan tekshiramiz
282 assert_eq!(unique_paths(4, 4), 20);
283 }
284}