- Baza halı və rekursiv addımı olan funksiya yazmaq və çağırışlar stekini izləmək
- Məsələnin DP ilə həll oluna biləcəyini tanımaq və rekurrent münasibət qurmaq
- Çanta və LCS cədvəllərini doldurmaq və optimal həlli bərpa etmək
- Acgöz alqoritmin nə vaxt səhv etdiyini göstərmək
Fibonaççi ədədlərini F(n) = F(n − 1) + F(n − 2) düsturu ilə birbaşa proqramlaşdırsan, F(40) üçün kompüter yüz milyondan çox funksiya çağırışı edəcək. Cəmi bir neçə sətir əlavə etməklə isə eyni proqram F(90)-ı da göz qırpımında tapır. Bu dərsdə bu «sehrin» — dinamik proqramlaşdırmanın necə işlədiyini, əvvəlcə isə onun əsası olan rekursiyanı öyrənəcəyik.
Rekursiya və çağırışlar steki
Funksiyanın məsələni özünün daha kiçik nüsxəsi vasitəsilə həll etməsi. Hər rekursiv funksiyanın iki hissəsi var: baza halı (cavab birbaşa məlumdur, rekursiya dayanır) və rekursiv addım (məsələ baza halına doğru kiçildilir).
- n · (n − 1)!rekursiv addım
- 0! = 1baza halı
fact(n) funksiyası n == 0 olanda 1, əks halda n * fact(n - 1) qaytarır. fact(4) çağırılanda stekdə nə baş verir?
Həllini göstərHəllini gizlət
fact(4) → fact(3) → fact(2) → fact(1) → fact(0) = 1 — baza halı, stekdə 5 çərçivə var.
Qalxma (çərçivələr tərs sıra ilə bağlanır):
fact(1) = 1 · 1 = 1
fact(2) = 2 · 1 = 2
fact(3) = 3 · 2 = 6
fact(4) = 4 · 6 = 24.
Vaxt O(n), stek yaddaşı da O(n) — hər çağırış cavab gələnə qədər stekdə gözləyir.
Təkrarlanan alt məsələlər və memoizasiya
Sadə rekursiv Fibonaççidə fib(5) iki dəfə fib(3), üç dəfə fib(2) çağırır — eyni alt məsələlər təkrar-təkrar həll olunur. Çağırışların sayı cavabın özü kimi eksponensial artır: calls(n) = 2F(n + 1) − 1. Memoizasiya (yuxarıdan aşağı) hər alt məsələnin cavabını lüğətdə saxlayır və ikinci dəfə hesablamır; cədvəlləşdirmə (aşağıdan yuxarı) isə cavabları kiçikdən böyüyə dövr ilə doldurur.
- T(n)sadə rekursiv fib(n)-in iş vaxtı
- φqızıl nisbət
Memoizasiya ilə hər fib(k) bir dəfə hesablanır: n + 1 alt məsələ × O(1) iş = O(n). Eksponensialdan xəttiyə!
from functools import lru_cache
calls = 0
def fib_naive(n):
global calls
calls += 1
return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)
@lru_cache(maxsize=None)
def fib_memo(n):
return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)
def fib_table(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
print(fib_naive(25), 'naive calls:', calls)
print(fib_memo(25), 'memo calls:', fib_memo.cache_info().misses)
print(fib_table(90))▸ Gözlənilən nəticə
75025 naive calls: 242785 75025 memo calls: 26 2880067194370816120
lru_cache ilə isə cəmi 26 fərqli alt məsələ hesablanır. Cədvəl versiyası O(1) yaddaşla F(90)-ı dərhal tapır.Klassik DP: çanta məsələsi və LCS
0/1 çanta məsələsi: tutumu W olan çantaya çəkiləri wᵢ, qiymətləri vᵢ olan əşyalardan elələrini seç ki, ümumi qiymət maksimum olsun (hər əşya ya götürülür, ya yox). i-ci əşya üçün iki seçim var — götürməmək və ya götürmək; ən yaxşısını saxlayırıq.
- dp[i][c]ilk i əşya ilə c tutumunda əldə edilən ən böyük qiymət
- wᵢ, vᵢi-ci əşyanın çəkisi və qiyməti (ikinci variant yalnız wᵢ ≤ c olanda)
Vaxt və yaddaş O(n · W). Bu, psevdopolinomialdır: W ədədinin bitlərinin sayına görə eksponensialdır.
W = 5. Əşyalar (çəki, qiymət): 1: (1, 1), 2: (2, 3), 3: (3, 4), 4: (4, 5). Maksimal qiyməti və seçilən əşyaları tap.
Həllini göstərHəllini gizlət
i = 1: [0, 1, 1, 1, 1, 1]
i = 2: [0, 1, 3, 4, 4, 4] (məs., c = 3: max(1, dp[1][1] + 3 = 4) = 4)
i = 3: [0, 1, 3, 4, 5, 7] (c = 5: max(4, dp[2][2] + 4 = 7) = 7)
i = 4: [0, 1, 3, 4, 5, 7] (c = 5: max(7, dp[3][1] + 5 = 6) = 7)
Cavab dp[4][5] = 7.
Bərpa: dp[4][5] = dp[3][5] → 4 götürülməyib; dp[3][5] = 7 ≠ dp[2][5] = 4 → 3 götürülüb, c = 5 − 3 = 2; dp[2][2] = 3 ≠ dp[1][2] = 1 → 2 götürülüb, c = 0.
Seçim: 2 və 3 (çəki 2 + 3 = 5, qiymət 3 + 4 = 7).
def knapsack(items, W):
n = len(items)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i, (w, v) in enumerate(items, start=1):
for c in range(W + 1):
dp[i][c] = dp[i - 1][c]
if w <= c:
dp[i][c] = max(dp[i][c], dp[i - 1][c - w] + v)
chosen, c = [], W
for i in range(n, 0, -1):
if dp[i][c] != dp[i - 1][c]:
chosen.append(i)
c -= items[i - 1][0]
return dp[n][W], sorted(chosen), dp
best, chosen, dp = knapsack([(1, 1), (2, 3), (3, 4), (4, 5)], 5)
for row in dp:
print(row)
print('best value:', best, '| items:', chosen)▸ Gözlənilən nəticə
[0, 0, 0, 0, 0, 0] [0, 1, 1, 1, 1, 1] [0, 1, 3, 4, 4, 4] [0, 1, 3, 4, 5, 7] [0, 1, 3, 4, 5, 7] best value: 7 | items: [2, 3]
Ən uzun ortaq altardıcıllıq (LCS): iki sətirdə eyni sıra ilə (mütləq yanaşı olmadan) rast gəlinən ən uzun simvollar ardıcıllığı. «ABCBDAB» və «BDCABA» üçün LCS uzunluğu 4-dür, məsələn, «BCBA». LCS diff və git-in fayl müqayisəsinin, DNT ardıcıllıqlarının tutuşdurulmasının əsasındadır.
- L[i][j]a-nın ilk i və b-nin ilk j simvolunun LCS uzunluğu
- L[0][j] = L[i][0]0 (boş sətirlə ortaq heç nə yoxdur)
Vaxt O(m · n): uzunluqları 1000 olan iki sətir üçün cəmi 10⁶ xana, halbuki bütün altardıcıllıqları yoxlamaq 2¹⁰⁰⁰ variant deməkdir.
def lcs(a, b):
dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
out, i, j = [], len(a), len(b)
while i and j:
if a[i - 1] == b[j - 1]:
out.append(a[i - 1])
i, j = i - 1, j - 1
elif dp[i - 1][j] >= dp[i][j - 1]:
i -= 1
else:
j -= 1
return dp[-1][-1], ''.join(reversed(out))
print(lcs('ABCBDAB', 'BDCABA'))
print(lcs('AGGTAB', 'GXTXAYB'))▸ Gözlənilən nəticə
(4, 'BCBA') (4, 'GTAB')
Acgöz alqoritm, yoxsa DP?
Acgöz alqoritm hər addımda o an ən yaxşı görünən seçimi edir və geri qayıtmır. O, sürətli və sadədir, amma yalnız «acgöz seçim xassəsi» olan məsələlərdə düzgün işləyir: Kruskal, Deykstra, Huffman kodlaşdırması, hissə-hissə götürülə bilən çanta. DP isə bütün variantları təkrarsız müqayisə edir və optimal alt struktur ilə təkrarlanan alt məsələlər olan hər yerdə düzgün cavab verir.
- coins[x]x məbləğini yığmaq üçün ən az sikkə sayı
- cmövcud sikkə nominalı
Sikkələr {1, 3, 4}, məbləğ 6. Acgöz alqoritm (həmişə ən böyük sikkə) neçə sikkə işlədir? Optimal cavab nədir?
Həllini göstərHəllini gizlət
DP cədvəli coins[0 … 6]:
coins[1] = 1, coins[2] = 2, coins[3] = 1, coins[4] = 1,
coins[5] = 1 + min(coins[4], coins[2], coins[1]) = 1 + 1 = 2,
coins[6] = 1 + min(coins[5], coins[3], coins[2]) = 1 + 1 = 2.
Optimal: 2 sikkə (3 + 3). İlk addımda «ən böyüyü götürmək» düzgün yolu bağladı.
def min_coins(coins, amount):
dp = [0] + [float('inf')] * amount
for x in range(1, amount + 1):
for c in coins:
if c <= x:
dp[x] = min(dp[x], dp[x - c] + 1)
return dp[amount], dp
def greedy_coins(coins, amount):
count = 0
for c in sorted(coins, reverse=True):
count += amount // c
amount %= c
return count
best, table = min_coins([1, 3, 4], 6)
print('greedy:', greedy_coins([1, 3, 4], 6), '| DP:', best, '| table:', table)
print('greedy:', greedy_coins([1, 5, 6, 9], 11), '| DP:', min_coins([1, 5, 6, 9], 11)[0])▸ Gözlənilən nəticə
greedy: 3 | DP: 2 | table: [0, 1, 2, 1, 1, 2, 2] greedy: 3 | DP: 2
| Üsul | İdeya | Nə vaxt düzgündür | Nümunə |
|---|---|---|---|
| Böl və idarə et | müstəqil alt məsələlər | alt məsələlər təkrarlanmayanda | birləşdirmə ilə çeşidləmə |
| Dinamik proqramlaşdırma | təkrarlanan alt məsələlərin cavabını yadda saxla | optimal alt struktur + təkrarlanan alt məsələlər | çanta, LCS, sikkələr |
| Acgöz | həmişə yerli ən yaxşı seçim | acgöz seçim xassəsi isbat olunanda | Kruskal, Deykstra, Huffman |
Əsas fikirlər
- Rekursiyanın baza halı və ona yaxınlaşan rekursiv addımı olmalıdır; hər çağırış stekdə çərçivə tutur.
- Sadə rekursiv Fibonaççi Θ(φⁿ), memoizasiya və ya cədvəl ilə O(n)-dir.
- DP şərtləri: optimal alt struktur və təkrarlanan alt məsələlər; resept: vəziyyət, keçid, baza, sıra.
- 0/1 çanta O(nW), LCS O(mn); cavab cədvəldən geriyə gedərək bərpa olunur.
- Acgöz alqoritm sürətlidir, amma yalnız acgöz seçim xassəsi olanda optimaldır ({1, 3, 4} ilə 6: 3 yox, 2 sikkə).
Özünü yoxla
10 sual. Hər düzgün cavab XP qazandırır.