House Robber

Q: House Robber için bağıntı nedir?

İlk k evden elde edilen en iyi toplam max(best[k-1], best[k-2] + nums[k-1]) değeridir. Ya k-1 numaralı evi atlayıp ondan önceki evlerden elde edilen en iyi sonucu korursun ya da k-1 numaralı evi alıp komşusundan önce biten en iyi sonuca eklersin. Temel durumlar, hiç ev olmaması için 0 ve tek ev olması için nums[0] değeridir.

Q: Her iki evden birini soymak, Ev Soyguncusu problemini neden çözmüyor?

En iyi plan bazen arka arkaya iki evi atlar. [10, 1, 1, 10] dizisinde çift sıradaki evlerin toplamı da tek sıradaki evlerin toplamı da 11'dir; ilk ve son evi almak ise 20 verir. Dinamik programlama, her evde atlamayı ve almayı karşılaştırır, böylece bu planları bulur.

OrtaDinamik programlama

+10

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

Fonksiyon

rob(nums: integer-array) → integer

numsinteger-array: sokak sırasına göre her evdeki para
Döndürürinteger: Birbirine bitişik 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 elde etmek için 0 ve 3 numaralı evlerden 5 ve 11'i alın. Art arda iki evi atlamak serbesttir ve burada diğer tüm planlardan daha iyi sonuç verir: 5 + 4 + 2 = 11 ve 3 + 11 = 14.

Gönderirken +16 gizli test

Ek soru

Alınacak evleri ve toplamı döndür. Bu listeyi yeniden oluşturmak için tablodan neleri saklaman gerekiyor ve iki ara toplam bunu 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

Açık kestirme yollar işe yaramaz. İkişer ev atlayarak seçim yapmak, [5, 3, 4, 11, 2] örneğindeki 5 ve 11 gibi, arka arkaya iki evi atlayan planları kaçırır; en zengin evi önce seçmek de [3, 4, 3] örneğinde başarısız olur; burada 4, toplam değeri 6 olan iki evi engeller. İşe yarayan yöntem, her seferinde bir eve karar vermektir: Bir eve kadar elde edilebilecek en yüksek toplam, yalnızca ondan önceki iki eve kadar elde edilebilecek en yüksek toplamlara bağlıdır.

Her evde her iki seçeneği de dene

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

Sezgi

Son eve, n-1 numaralı eve bakın. Her plan ya bu evi atlar ya da eve girer. Evi atlarsa yapabileceği en iyi şey, ilk n-1 ev için en iyi planı seçmektir. Evi alırsa n-2 numaralı eve giremez; bu yüzden nums[n-1] değerini ilk n-2 ev için en iyi plana ekler. Yanıtlardan büyük olanı sonuçtur.

Bunu, ilk k evden alabileceğiniz en yüksek miktarı döndüren most(k) fonksiyonu olarak yazın: most(k) = max(most(k-1), most(k-2) + nums[k-1]); hiç ev olmadığında most(0) = 0, bir ev olduğunda most(1) = nums[0]. Her plan son evi ya atlar ya da alır; dolayısıyla iki dal da tüm planları kapsar ve sonuç doğrudur.

Yavaştır, çünkü dallar örtüşür. most(k-1), most(k-2) fonksiyonunu yeniden çağırır; böylece aynı soru tekrar tekrar yanıtlanır ve çağrı sayısı Fibonacci sayıları gibi, yaklaşık 1.6^n hızında artar. Kırk ev bile 300 milyondan fazla çağrı gerektirir ve testlerde 10^4 eve kadar çıkılır. Çağrılar ayrıca n seviye derinliğe kadar iç içe geçer ve Python'un varsayılan 1000 sınırını aşar.

Algoritma

İlk k evden alabileceğin en yüksek miktarı döndüren bir yardımcı most(k) yaz.
k 0 olduğunda 0, k 1 olduğunda 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. Yanıt 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; dolayısıyla n + 1 farklı soru vardır. Her birini bir kez yanıtlayıp bir tabloda saklayın ve okuduğunuz her yanıtın önceden tabloda bulunduğu bir sırayla tabloyu doldurun. Tabloyu dört karar tanımlar.

Durum: best[k], ilk k evden alabileceğiniz en yüksek miktardır. Özyineleme bağıntısı: best[k] = max(best[k-1], best[k-2] + nums[k-1]): k-1 numaralı evi atlayın ya da komşusundan önce biten en iyi sonuca bu evi ekleyerek alın. Temel durumlar: best[0] = 0 ve best[1] = nums[0]. Sıra: k için 2'den n'ye kadar ilerleyin; çünkü her girdi kendisinden önceki iki girdiyi okur.

[5, 3, 4, 11, 2] için tablo 0, 5, 5, 9, 16, 16 olur. k = 4 olduğunda, değeri best[3] = 9 olan 3 numaralı evi atlamayı, 11'i best[2] = 5 üzerine ekleyerek almayla karşılaştırırsınız; 16 kazanır. Yanıt son girdidir. Her girdi için bir karşılaştırma yapılır, bu nedenle zaman karmaşıklığı O(n), tablonun alan karmaşıklığı ise O(n)'dir.

Algoritma

n + 1 girişli bir best tablosu oluştur.
best[0] = 0 ve best[1] = nums[0] olarak ayarla.
2'den n'ye kadar k için best[k] değerini best[k-1] ve best[k-2] + nums[k-1] değerlerinden büyük olanına 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 çalışan toplam

Sezgi

Tablonun her girdisi yalnızca kendisinden hemen önceki iki girdiyi okur. best[k] bilindikten sonra best[k-2] bir daha okunmaz. Bu yüzden tablo yerine iki sayı tut: twoBack, iki ev önceye kadarki en iyi toplam; ve oneBack, bir önceki eve kadarki en iyi toplam.

x değerini taşıyan bir ev için yeni en iyi değer max(oneBack, twoBack + x) olur. Sonra değerleri kaydır: twoBack eski oneBack değerini, oneBack ise yeni en iyi değeri alır. İkisi de 0'dan başlar; bu, ilk evden önceki boş sokağı temsil eder. Böylece ilk ev için özel bir duruma gerek kalmaz: en iyi değer max(0, 0 + nums[0]) olur.

[5, 3, 4, 11, 2] için ikili sırasıyla (0, 0), (0, 5), (5, 5), (5, 9), (9, 16), (16, 16) olur ve oneBack 16 değerinde kalır. İşlem miktarı tabloyla aynı, O(n); bellek kullanımı ise O(1)'e düşer.

Algoritma

twoBack ve oneBack değerlerini 0 olarak ayarla.
nums içindeki her x miktarı 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

Çoğu yanlış yanıt, küçük girdilerde işe yarayan bir kestirme yöntemden veya iki toplamı yanlış sırayla güncellemekten kaynaklanır.

Çift numaralı evleri ve tek numaralı evleri toplamak ve büyük olanı almak, arka arkaya iki evi atlayan planları gözden kaçırır. [10, 1, 1, 10] için her iki toplam da 11’dir, ancak 0 ve 3 numaralı evler 20 eder.
En zengin evi önce seçmek [3, 4, 3] için başarısız olur: 4’ü alır ve birlikte 6 eden iki 3’ü de engeller.
oneBack değerini twoBack içine kopyalamadan önce üzerine yazmak, sonraki evin ihtiyaç duyduğu değeri kaybettirir. Önce yeni en iyi değeri hesaplayın, sonra kaydırın veya dilim izin veriyorsa ikisini birden atayın.
nums[1] değerini okumak ya da best[1] ve best[2] değerlerini baştan ayarlamak, tek evli bir sokakta sorun çıkarır. Her iki toplamı da 0’dan başlatmak özel durumu ortadan kaldırır.
Lua ve R’de diziler 1’den başladığı için, k-1 numaralı evdeki para nums[k] değeridir.

Sıkça sorulan sorular4

House Robber için bağıntı nedir?

İlk k evden elde edilen en iyi toplam max(best[k-1], best[k-2] + nums[k-1]) değeridir. Ya k-1 numaralı evi atlayıp ondan önceki evlerden elde edilen en iyi sonucu korursun ya da k-1 numaralı evi alıp komşusundan önce biten en iyi sonuca eklersin. Temel durumlar, hiç ev olmaması için 0 ve tek ev olması için nums[0] değeridir.

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

Dinamik programlama çözümü 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. Yanıtları saklamayan basit özyineleme yaklaşık 1.6^n çağrı yapar; bu üstel bir büyümedir.

Her iki evden birini soymak, Ev Soyguncusu problemini neden çözmüyor?

En iyi plan bazen arka arkaya iki evi atlar. [10, 1, 1, 10] dizisinde çift sıradaki evlerin toplamı da tek sıradaki evlerin toplamı da 11'dir; ilk ve son evi almak ise 20 verir. Dinamik programlama, her evde atlamayı ve almayı karşılaştırır, böylece bu planları bulur.

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

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