Komşu olmayan hasat
Görev tanımı
Problem
Bir hasat robotu tek sıra tarlalar boyunca ilerliyor ve her tarlanın bilinen bir verimi var. Kolu her toplamadan sonra dinlenmeye ihtiyaç duyuyor, bu yüzden yan yana duran iki tarlayı asla hasat edemez. Robotun tek geçişte toplayabileceği en büyük toplam verimi döndür. Verimler 0'dan başlayan tam sayılar ve sıra boş olabilir.
Örnekler
Input: yields = [2, 7, 9, 3, 1]
Output: 12
Neden: 0, 2 ve 4 numaralı tarlaları 2 + 9 + 1 için hasat et
Input: yields = [5, 1, 1, 5]
Output: 10
Neden: iki uç tarla komşu değil, ikisi de alınabilir
Input: yields = []
Output: 0
Neden: edge case: boş sıra hiçbir verim vermez
İpuçları
0 / 3
Önce en büyük tarlayı seçmek iki iyi komşuyu engelleyebilir. Sırayı bir kerede değil, tarla tarla düşün.
Bir tarlaya vardığında tam olarak tek bir kararla karşılaşırsın: hasat et ya da atla. Her seçim yalnız hemen önceki tarlada olana bağlı.
İki kümülatif toplam taşı: önceki tarla hasat edildiyse en iyi sonuç ve atlandıysa en iyi sonuç. Mevcut tarlayı hasat etmek atlanan toplamı uzatır; atlamak ikisinin iyisini korur.
- Hedef zaman
- O(n)
- Hedef alan
- O(1)
Kısıtlar
- yields are integers ≥ 0
- the row may be empty
Çözüm
Her tarlada şimdiye kadarki en iyi toplam iki durumdan birinden gelir: önceki tarla hasat edildi ya da edilmedi. Mevcut tarlayı hasat etmeye yalnız atlanmış durumdan izin vardır, atlamak da hangi durum daha iyiyse onu korur; böylece iki değişken bütün bir tablonun yerini alır. Cevap son tarladan sonraki daha iyi durumdur. Tek geçişle zaman O(n), alan O(1).
def best_harvest(yields):
took, skipped = 0, 0 # best total if the last plot was harvested / left alone
for y in yields:
# harvesting now needs the previous plot skipped; skipping keeps the better state
took, skipped = skipped + y, max(took, skipped)
return max(took, skipped)
print(best_harvest([2, 7, 9, 3, 1])) # -> 12
print(best_harvest([5, 1, 1, 5])) # -> 10
print(best_harvest([])) # -> 0Kodda değil de fikirde mi takıldın? House Robber bunu anlatıyor.