House Robber

Q: Her iki evden birini almak, House Robber problemini neden çözmez?

En iyi plan bazen arka arkaya iki evi atlar. [10, 1, 1, 10] dizisinde çift sıradaki evlerin ve tek sıradaki evlerin toplamı 11 iken ilk ve son evin toplamı 20'dir.

OrtaDinamik programlama

+10

Evler bir cadde boyunca sıra hâlinde dizilmiştir ve nums[i], i numaralı evdeki para miktarıdır. İstediğin evlerden para alabilirsin, ancak yan yana duran iki evden asla alamazsın. Alabileceğin en büyük toplamı döndür.

Fonksiyon

rob(nums: integer-array) → integer

numsinteger-array: her evdeki para, sokak sırasına göre
Döndürürinteger: Yan yana iki evden almadan alabileceğin en büyük toplam

Kısıtlar

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 1000
Yanıt en fazla 5 × 10⁶, bu nedenle işaretli 32 bitlik bir tam sayıya sığar.

Örnekler

Girdi: nums = [5, 3, 4, 11, 2]
Çıktı: 16
Açıklama: 16 için 0 ve 3 numaralı evlerden 5 ve 11'i al. Arka arkaya iki evi atlamak serbesttir ve burada diğer tüm planlardan daha iyi sonuç verir: 5 + 4 + 2 = 11 ve 3 + 11 = 14.

Ek soru

Alınacak evleri ve toplamı döndür. Bu listeyi yeniden oluşturmak için tablodan neyi saklamalısın ve bunu iki birikimli toplam hâlâ yapabilir mi?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Kestirme yollar işe yaramaz: birer ev atlayarak ilerlemek [5, 3, 4, 11, 2] dizisinde 5 ve 11’i kaçırır; en zengin evi önce seçmek ise [3, 4, 3] dizisinde daha kötü sonuç verir. Bunun yerine her seferinde bir eve karar ver: Bir eve kadar elde edilebilecek en iyi toplam, yalnızca ondan önceki iki eve kadar elde edilebilecek en iyi toplamlara bağlıdır.

Her evde her iki seçeneği de dene

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Her plan ya son evi atlar ya da alır. Atlamak, ilk n-1 ev için en iyi planı bırakır; almak ise ilk n-2 ev için en iyi plana nums[n-1] ekler. Dolayısıyla most(k) = max(most(k-1), most(k-2) + nums[k-1]); burada most(0) = 0 ve most(1) = nums[0]. İki dal tüm planları kapsar, bu yüzden yanıt doğrudur.

Dallar örtüşür: most(k-1), most(k-2) değerini yeniden hesaplar ve çağrıların sayısı Fibonacci sayıları gibi, yaklaşık 1.6^n hızında büyür. Kırk ev 300 milyondan fazla çağrı gerektirir ve n değeri 10^4'e ulaşır.

Algoritma

İlk k evden alabileceğin en yüksek miktarı döndüren bir yardımcı most(k) yaz.
k 0 ise 0, 1 ise nums[0] döndür.
Aksi takdirde skip = most(k-1) ve take = most(k-2) + nums[k-1] değerlerini hesapla.
İkisinden büyük olanı döndür. Cevap most(n) olur.

def rob(nums):
    def most(k):
        # The most you can take from the first k houses
        if k == 0:
            return 0
        if k == 1:
            return nums[0]
        # Skip house k-1, or take it and skip house k-2
        return max(most(k - 1), most(k - 2) + nums[k - 1])

    return most(len(nums))

Alttan üste tablo

Sezgi

Özyineleme yalnızca most(0) ile most(n) arasındakileri sorar: n + 1 soru. Her birini bir best tablosunda bir kez yanıtla; best[0] = 0 ve best[1] = nums[0] değerleriyle başla ve k = 2 değerinden itibaren yukarı doğru doldur; böylece her yanıtın okuduğu iki değer de önceden tabloda bulunur.

[5, 3, 4, 11, 2] için tablo 0, 5, 5, 9, 16, 16 olur. k = 4 olduğunda, 3. evi atlamak best[3] = 9 değerini korurken, 11'i best[2] = 5 değerinin üzerine eklemek 16 verir ve bu değer kazanır. Her girdi bir karşılaştırma gerektirir: O(n) zaman ve O(n) alan.

Algoritma

n + 1 girişli bir best tablosu oluştur.
best[0] = 0 ve best[1] = nums[0] değerlerini ata.
2'den n'ye kadar her k için best[k] değerini, best[k-1] ile best[k-2] + nums[k-1] değerlerinden büyük olana ayarla.
best[n] değerini döndür.

def rob(nums):
    n = len(nums)
    # best[k] is the most you can take from the first k houses
    best = [0] * (n + 1)
    best[1] = nums[0]
    for k in range(2, n + 1):
        # Skip house k-1, or take it on top of the best from the first k-2 houses
        best[k] = max(best[k - 1], best[k - 2] + nums[k - 1])
    return best[n]

İki birikimli toplam

Sezgi

Her giriş yalnızca kendisinden önceki iki girişi okur; bu yüzden tablo yerine iki sayı tut: iki ev geriye kadar olan en iyi toplamlar için twoBack ve önceki eve kadar olan en iyi toplamlar için oneBack. x değerini içeren bir ev için yeni en iyi değer max(oneBack, twoBack + x) olur; ardından ikisini de birer adım kaydır. İlk evden önceki boş sokağı temsil ettikleri için ikisi de 0'dan başlar; böylece tek evli bir sokak için özel duruma gerek kalmaz. Zaman karmaşıklığı O(n) olarak kalır, bellek kullanımı ise O(1)'e düşer.

Algoritma

twoBack ve oneBack değerlerini 0 olarak ayarla.
nums içindeki her x değeri için current = max(oneBack, twoBack + x) değerini hesapla.
oneBack değerini twoBack içine, ardından current değerini oneBack içine taşı.
Son evden sonra oneBack değerini döndür.

def rob(nums):
    # The best totals from the houses up to two back and up to one back
    two_back, one_back = 0, 0
    for amount in nums:
        # Skip this house, or take it on top of the best from two back
        two_back, one_back = one_back, max(one_back, two_back + amount)
    return one_back

Tuzaklar ve uç durumlar

oneBack'i twoBack'e kopyalamadan önce üzerine yazmak. Sonraki ev yanlış toplamı okur. Önce yeni en iyi değeri hesaplayın, sonra değerleri kaydırın veya ikisini birden atayın.
nums[1]'i okumak ya da baştan best[1] ve best[2] değerlerini ayarlamak. İkisi de [0] gibi tek evli bir sokakta hata verir.
Lua ve R'de diziler 1'den başlar; bu yüzden k-1 numaralı evdeki para nums[k] olur.

Sıkça sorulan sorular3

House Robber'ın zaman ve uzay karmaşıklığı nedir?

Dinamik programlama her eve bir kez bakar, bu nedenle O(n) zaman alır. Tam bir tablo O(n) alan kullanır; yalnızca son iki toplamı tutmak bunu O(1)'e düşürür. Saklanan yanıtlar olmadan yapılan basit özyineleme yaklaşık 1.6^n çağrı yapar.

Her iki evden birini almak, House Robber problemini neden çözmez?

En iyi plan bazen arka arkaya iki evi atlar. [10, 1, 1, 10] dizisinde çift sıradaki evlerin ve tek sıradaki evlerin toplamı 11 iken ilk ve son evin toplamı 20'dir.

Evler bir daire oluşturduğunda House Robber problemini nasıl çözersin?

Bir çemberde ilk ve son ev komşudur, bu yüzden bir plan en fazla bu evlerden birini içerir. Düz sokak çözümünü iki kez çalıştır: bir kez son ev olmadan, bir kez de ilk ev olmadan; ardından daha büyük sonucu döndür. Tek ev varsa bu özel durumdur: yanıt o evdir.