Uy o'g'risi (House Robber)

Ko'cha bo'ylab joylashgan uylar, har birida ma'lum miqdorda qiymatli narsa bor. O'g'ri bir kechada maksimal narsani o'g'irlashni istaydi. Cheklov: qo'shni uylarni ketma-ket o'g'irlab bo'lmaydi — signalizatsiya ishga tushadi.

Har uydagi qiymatlar massivi berilgan. Qo'shni uylarni tanlamasdan o'g'irlash mumkin bo'lgan maksimal qiymatni toping.

Kirish: [1, 2, 3, 1]
Chiqish: 4
Izoh: uy 0 (1) + uy 2 (3) = 4

Kirish: [2, 7, 9, 3, 1]
Chiqish: 12
Izoh: uy 0 (2) + uy 2 (9) + uy 4 (1) = 12

Kirish: [2, 1, 1, 2]
Chiqish: 4
Izoh: uy 0 (2) + uy 3 (2) = 4

Asosiy g'oya: har uy uchun qaror

i-uyga kelganda ikki tanlov:

O'g'irlanadi: nums[i] + dp[i-2] — bu uy qiymati + i-2 gacha optimal.
O'g'irlanmaydi: dp[i-1] — oldingi uy gacha optimal, shu uyni o'tkazib yuborish.

Rekurrentlik:

dp[i] = MAX(dp[i-1], dp[i-2] + nums[i])

dp[i] — i-uy gacha (shu uy kirgan holda yoki kiritmasdan) olinishi mumkin bo'lgan maksimal qiymat.

Base caselar:

dp[0] = nums[0] — bitta uy, uni olish
dp[1] = MAX(nums[0], nums[1]) — ikkitadan kattaroqni olish

DP jadvali bilan

FUNCTION ROB(nums)
    n = LENGTH(nums)

    IF n = 0    RETURN 0
    IF n = 1    RETURN nums[0]

    dp    = n ta 0 qiymatdan iborat array
    dp[0] = nums[0]
    dp[1] = MAX(nums[0], nums[1])

    FOR i = 2 DAN n - 1 GACHA
        dp[i] = MAX(dp[i - 1], dp[i - 2] + nums[i])

    RETURN dp[n - 1]

Xotira optimallashtirish

dp[i] faqat dp[i-1] va dp[i-2] ga bog'liq:

FUNCTION ROB_OPTIMAL(nums)
    n = LENGTH(nums)

    IF n = 0    RETURN 0
    IF n = 1    RETURN nums[0]

    prev2 = nums[0]
    prev1 = MAX(nums[0], nums[1])

    FOR i = 2 DAN n - 1 GACHA
        current = MAX(prev1, prev2 + nums[i])
        prev2   = prev1
        prev1   = current

    RETURN prev1

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

Bosqichma-bosqich dry run

nums = [2, 7, 9, 3, 1]:

prev2 = 2            // dp[0] = nums[0]
prev1 = MAX(2, 7) = 7  // dp[1] = MAX(nums[0], nums[1])

i=2, nums[2]=9:
  current = MAX(7, 2+9) = MAX(7, 11) = 11
  prev2=7, prev1=11

i=3, nums[3]=3:
  current = MAX(11, 7+3) = MAX(11, 10) = 11
  prev2=11, prev1=11

i=4, nums[4]=1:
  current = MAX(11, 11+1) = MAX(11, 12) = 12
  prev2=11, prev1=12

RETURN 12

dp jadvali: [2, 7, 11, 11, 12].

Tanlov: nums[0]=2, nums[2]=9, nums[4]=1 → 2 + 9 + 1 = 12.

Nima uchun greedy ishlamaydi?

[2, 7, 9, 3, 1] uchun greedy (kattasini tanlash) da 7 birinchi tanlanadi, keyin undan 2 uy o'tgan 1 tanlanadi — natija 7 + 1 = 8. Bu optimal emas.

O'g'ri har uyda faqat "bu uydagi narsani"ni ko'radi, lekin keyingi va undan keyingi uylar bilan kombinatsiyani ko'ra olmaydi. DP esa barcha kombinatsiyalarni saqlab, har qadam optimal yechimga qarab ketadi.

Vaqt va xotira murakkabligi

Yondashuv	Vaqt	Xotira
Rekursiya (memoizatsiyasiz)	`O(2^n)`	`O(n)`
Memoizatsiya	`O(n)`	`O(n)`
DP jadvali	`O(n)`	`O(n)`
Optimallashtirilgan	`O(n)`	`O(1)`

Edge case'lar

Bo'sh massiv. n = 0 → 0.

Bitta element. n = 1 → nums[0].

Ikkita element. n = 2 → MAX(nums[0], nums[1]).

Barcha bir xil. [5, 5, 5, 5] → qo'shni emas, toq indekslardan olish: 5 + 5 = 10.

Kamayuvchi. [5, 4, 3, 2, 1] → 5 + 3 + 1 = 9.

Nol qiymatli uylar. [0, 0, 5, 0, 5] → 5 + 5 = 10.

Kengaytirilgan variantlar

Uy o'g'risi II: dumaloq ko'cha

Uylar doira shaklida joylashgan — birinchi va oxirgi uy qo'shni. Cheklov bir xil.

Yondashuv: ikki alohida chiziqli masalani yechish: 1. Birinchi uydan oxirgi uyni chiqarib: nums[0..n-2] 2. Ikkinchi uydan oxirgi uyni kiritib: nums[1..n-1]

FUNCTION ROB_CIRCLE(nums)
    n = LENGTH(nums)
    IF n = 1    RETURN nums[0]
    RETURN MAX(ROB_OPTIMAL(nums[0..n-2]), ROB_OPTIMAL(nums[1..n-1]))

Daraxt uy o'g'risi

Uylar daraxt ko'rinishida — qo'shni = ota-bola aloqasi. DFS + DP kombinatsiyasi.

Xulosa

Uy o'g'risi — 1D DP ning klassik namunasi. Rekurrentlik: dp[i] = MAX(dp[i-1], dp[i-2] + nums[i]). Har uyda "olaman yoki olmaymanmi?" — bu ikki tanlovning maksimali.

Optimallashtirilgan yechim ikkita o'zgaruvchi bilan O(n) vaqt, O(1) xotirada ishlaydi.