Evleri ucuza boya
Görev tanımı
Problem
Bir sıradaki her ev üç renkten biriyle boyanmalı ve belirli bir evi belirli bir renge boyamanın kendi fiyatı var. Komşu evler aynı rengi paylaşamaz. Bütün sırayı boyamanın en ucuz toplam fiyatını döndür.
Örnekler
Input: costs = [[17, 2, 17],
[16, 16, 5],
[14, 3, 19]]
Output: 10
Neden: evleri ikinci, üçüncü ve ikinci renge 2 + 5 + 3'e boya
Input: costs = [[7, 6, 2]]
Output: 2
Neden: tek bir ev basitçe en ucuz rengini alır
Input: costs = []
Output: 0
Neden: edge case: boş sıra hiçbir şeye mal olmaz
İpuçları
0 / 3
Her ev için en ucuz rengi bağımsız olarak seçmek başarısız olabilir, çünkü ucuz bir seçim yan evde pahalı bir seçimi zorunlu kılabilir. Kararın kendisinden sonra geleni hesaba katması gerekir.
Sırayı bir kez dolaş ve renk başına bir tane olmak üzere üç kümülatif cevap taşı: bu ev o renkte bittiğine göre buraya kadar her şeyi boyamanın en ucuz yolu.
Her yeni ev, bir renk için kendi fiyatını alır ve diğer iki rengin kümülatif cevaplarından ucuz olanını ekler. Üç yeni değerin hepsini üç eskiden aynı anda hesapla, sonra devam et; sondaki üçün en küçüğünü al.
- Hedef zaman
- O(n)
- Hedef alan
- O(1)
Kısıtlar
- each house has exactly three colour prices
Çözüm
Sıranın geri kalanının umursadığı tek şey az önce boyanan evin rengidir; bu yüzden renk başına bir tane olmak üzere üç kümülatif toplam bütün geçmişi yakalar. Her ev bu üçünü öncekilerden, kendi fiyatını çakışan iki seçeneğin ucuzuna ekleyerek yeniden kurar. Üçünü aynı anda hesaplamak önemli, çünkü az önce güncellenmiş bir değeri kullanmak bir evin kendisinden ödünç almasına izin verirdi. Yalnız üç sayı tutulduğu için zaman O(n), alan O(1).
def cheapest_painting(costs):
first = second = third = 0 # cheapest total ending in each of the colours
for a, b, c in costs:
# each colour pays its own price plus the better of the other two histories
first, second, third = (a + min(second, third),
b + min(first, third),
c + min(first, second))
return min(first, second, third)
print(cheapest_painting([[17, 2, 17], [16, 16, 5], [14, 3, 19]])) # -> 10
print(cheapest_painting([[7, 6, 2]])) # -> 2
print(cheapest_painting([])) # -> 0Kodda değil de fikirde mi takıldın? Dinamik programlama nedir? bunu anlatıyor.