Zinapoyaga chiqish

n ta zinapoya bor. Har safar 1 yoki 2 ta zinapoyaga sakrash mumkin. Tepaga chiqishning necha xil yo'li bor?

Kirish: n = 2
Chiqish: 2
Izoh: [1+1] va [2] — ikki yo'l

Kirish: n = 3
Chiqish: 3
Izoh: [1+1+1], [1+2], [2+1] — uch yo'l

Kirish: n = 5
Chiqish: 8

Masalani kichikroqqa qisqartirish

n-zinapoyaga yetishdan oldin nima bo'lishi mumkin? Faqat ikki variant:

n-1-zinapoyadan 1 qadam sakrash
n-2-zinapoyadan 2 qadam sakrash

Demak:

ways(n) = ways(n-1) + ways(n-2)

Bu Fibonacci ketma-ketligi. ways(1) = 1, ways(2) = 2 boshlanish holatlari.

Base caselar:

n = 1 → 1 yo'l: [1]
n = 2 → 2 yo'l: [1+1], [2]

Rekursiv yechim (memoizatsiyasiz)

FUNCTION CLIMB(n)
    IF n = 1    RETURN 1
    IF n = 2    RETURN 2
    RETURN CLIMB(n - 1) + CLIMB(n - 2)

Bu eksponensial vaqt oladi — CLIMB(n-2) bir necha marta hisoblanadi. n = 50 da millionlab takroriy hisoblash.

Memoizatsiya bilan

memo = bo'sh map

FUNCTION CLIMB(n)
    IF n = 1    RETURN 1
    IF n = 2    RETURN 2
    IF n memo ichida bor
        RETURN memo[n]
    result  = CLIMB(n - 1) + CLIMB(n - 2)
    memo[n] = result
    RETURN result

Har qiymat bir marta hisoblanadi. Vaqt: O(n), xotira: O(n).

DP jadvali bilan (bottom-up)

FUNCTION CLIMB_DP(n)
    IF n = 1    RETURN 1
    IF n = 2    RETURN 2

    dp    = n + 1 ta 0 qiymatdan iborat array
    dp[1] = 1
    dp[2] = 2

    FOR i = 3 DAN n GACHA
        dp[i] = dp[i - 1] + dp[i - 2]

    RETURN dp[n]

Xotira optimallashtirilgan yechim

dp[i] faqat dp[i-1] va dp[i-2] ga bog'liq. Butun jadvalni saqlash shart emas:

FUNCTION CLIMB_OPTIMAL(n)
    IF n = 1    RETURN 1
    IF n = 2    RETURN 2

    prev2 = 1   // dp[i-2]
    prev1 = 2   // dp[i-1]

    FOR i = 3 DAN n GACHA
        current = prev1 + prev2
        prev2   = prev1
        prev1   = current

    RETURN prev1

Vaqt: O(n), xotira: O(1).

Bosqichma-bosqich dry run: n = 5

prev2 = 1  (ways(1))
prev1 = 2  (ways(2))

i=3: current = 2+1 = 3,  prev2=2, prev1=3
i=4: current = 3+2 = 5,  prev2=3, prev1=5
i=5: current = 5+3 = 8,  prev2=5, prev1=8

RETURN 8

Tekshiruv:

n=1: [1]                                    → 1
n=2: [1+1], [2]                             → 2
n=3: [1+1+1], [1+2], [2+1]                 → 3
n=4: [1+1+1+1], [1+1+2], [1+2+1], [2+1+1], [2+2] → 5
n=5: 8 ta yo'l

Vaqt va xotira murakkabligi

Yondashuv	Vaqt	Xotira
Oddiy rekursiya	`O(2^n)`	`O(n)` call stack
Memoizatsiya	`O(n)`	`O(n)`
DP jadvali	`O(n)`	`O(n)`
Optimallashtirilgan	`O(n)`	`O(1)`

Edge case'lar

n = 1: bir zinapoya — faqat bir yo'l: [1].

n = 2: ikki zinapoya — ikki yo'l: [1+1] va [2].

Katta n: javob tez o'sadi (Fibonacci kabi eksponensial). 32-bitli sonda n ≈ 46 dan keyin overflow. 64-bitli sonda n ≈ 90 dan keyin overflow.

Note

Bu masala Fibonacci bilan bir xil tuzilmada, lekin farq bor: fib(1) = 1, fib(2) = 1, ways(1) = 1, ways(2) = 2. Fibonacci jadvalida ways(n) = fib(n+1).

Kengaytirilgan variant: k ta qadam

Agar 1, 2, ..., k ta qadam sakrash mumkin bo'lsa:

FUNCTION CLIMB_K(n, k)
    dp    = n + 1 ta 0 qiymatdan iborat array
    dp[0] = 1    // 0-zinapoyada turish

    FOR i = 1 DAN n GACHA
        FOR j = 1 DAN MIN(i, k) GACHA
            dp[i] = dp[i] + dp[i - j]

    RETURN dp[n]

Vaqt: O(n × k), xotira: O(n).

Xulosa

Zinapoya masalasi DP ning endi o'rganilayotganlarga eng tipik namunasi. Rekurrentlik: ways(n) = ways(n-1) + ways(n-2). Optimallashtirilgan yechim faqat ikki o'zgaruvchi bilan O(n) vaqt va O(1) xotirada ishlaydi.