Grid boyunca en ucuz yol
Görev tanımı
Problem
Bir grid'in her hücresinde negatif olmayan bir maliyet var. Sol üst hücreden başlıyorsun ve yalnız sağa ya da aşağı giderek sağ alt hücreye ulaşmalısın. İlk ve son hücreler dahil, içinden geçtiğin hücrelerin maliyetlerinin mümkün olan en küçük toplamını döndür.
Örnekler
Input: grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
Output: 7
Neden: sağ, sağ, aşağı, aşağı 1, 3, 1, 1, 1'i ziyaret eder ve ortadaki 5'ten kaçınır
Input: grid = [[2, 1, 4], [3, 1, 1]]
Output: 5
Neden: sağ, aşağı, sağ 2, 1, 1, 1'i ziyaret eder
Input: grid = [[7]]
Output: 7
Neden: edge case: başlangıç aynı zamanda bitiş
İpuçları
0 / 3
Her adımda ucuz komşuyu seçmek bir tuzak, çünkü ucuz bir adım pahalı bir bölgeye götürebilir. Yol sayısı hepsini denemek için fazla hızlı büyür.
Bir hücreye girmenin tek yolları üstündeki ve solundaki hücrelerden. Yani bir hücreye ulaşmanın en ucuz maliyeti kendi maliyeti artı o iki en ucuz maliyetin ucuz olanıdır.
Grid boyutunda bir tablo kur. Sol üst eleman kendi maliyetidir, ilk satır yalnız soldan, ilk sütun yalnız yukarıdan gelebilir. Diğer her eleman maliyeti artı üstteki ve soldaki elemanların minimumudur. Cevap sağ alt eleman.
- Hedef zaman
- O(rows · cols)
- Hedef alan
- O(rows · cols)
Kısıtlar
- every cell cost is non-negative
Çözüm
Bir hücreye giren her yol yukarıdan ya da soldan gelir; bu yüzden ona ulaşmanın en ucuz yolu, bu iki en ucuz yolun ucuz olanını uzatır. Tabloyu satır satır doldurmak, bir hücre ihtiyaç duymadan önce iki komşunun da kesinleşmesini garanti eder. İlk satırın ve ilk sütunun (column) tek bir giriş yolu var, ayrı ele alınmalarının sebebi bu. Zaman O(rows · cols), alan O(rows · cols); her satır yalnız üstündeki satırı okuduğu için bellek önemliyse tablonun tek bir satırı yeter.
def cheapest_path(grid):
rows, cols = len(grid), len(grid[0])
cost = [[0] * cols for _ in range(rows)]
for r in range(rows):
for c in range(cols):
if r == 0 and c == 0:
cost[r][c] = grid[r][c]
elif r == 0:
cost[r][c] = cost[r][c - 1] + grid[r][c] # top row: only from the left
elif c == 0:
cost[r][c] = cost[r - 1][c] + grid[r][c] # left column: only from above
else:
cost[r][c] = min(cost[r - 1][c], cost[r][c - 1]) + grid[r][c]
return cost[-1][-1]
print(cheapest_path([[1, 3, 1], [1, 5, 1], [4, 2, 1]])) # -> 7
print(cheapest_path([[2, 1, 4], [3, 1, 1]])) # -> 5
print(cheapest_path([[7]])) # -> 7Kodda değil de fikirde mi takıldın? Grid'lerde DP bunu anlatıyor.