Izgaralarda Benzersiz Yollar ve Minimum Yol Toplamı
Engelli ve engelsiz benzersiz yollar için iki boyutlu DP tablosunu doldurun, ardından bunu bir yol üzerindeki değerlerin toplamını en aza indirecek şekilde uyarlayın.
Izgaralarda Benzersiz Yollar ve Minimum Yol Toplamı, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 1. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
Izgarada Benzersiz Yollar
Benzersiz Yollar (LeetCode 62) şu soruyu sorar: m×n boyutunda bir ızgarada, yalnızca sağa veya aşağı hareket ederek sol üst köşeden sağ alt köşeye kaç farklı yol gidebilirsiniz? 3×7 boyutundaki bir ızgara için yanıt 28'dir. Temel fikir şudur: (i,j) hücresine giden her yol ya (i-1,j) (üst) ya da (i,j-1) (sol) hücresinden gelmelidir; bu da doğal bir 2B DP formülasyonu sağlar.
# 3x7 grid: robot starts at (0,0), goes to (2,6)
# Must make exactly 2 down-moves and 6 right-moves
# Total moves = 8, choose 2 for down = C(8,2) = 28
import math
print('Unique paths 3x7:', math.comb(3+7-2, 3-1)) # 28
print('Unique paths 3x3:', math.comb(3+3-2, 3-1)) # 6
print('Unique paths 2x2:', math.comb(2+2-2, 2-1)) # 2Benzersiz Yollar için 2B DP Tablosu
dp[i][j] değerini (i,j) hücresine giden yol sayısı olarak tanımlayın. İlk satır ve ilk sütundaki tüm değerler 1'dir (üst satırdaki veya en soldaki sütundaki herhangi bir hücreye ulaşmanın yalnızca bir yolu vardır). Diğer hücreler için: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Tabloyu satır satır doldurun; yanıt dp[m-1][n-1] olur. Zaman karmaşıklığı: O(m×n), alan: O(m×n); bu değer O(n)'e düşürülebilir.
def unique_paths(m, n):
dp = [[1] * n for _ in range(m)]
# First row and column stay as 1s (base cases)
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
print(unique_paths(3, 7)) # 28
print(unique_paths(3, 3)) # 6
print(unique_paths(1, 1)) # 1 (already at destination)O(n) Alanına Optimizasyon
dp[i][j] yalnızca geçerli satıra ve önceki satıra bağlı olduğundan, 2B tablonun tamamını tek bir 1B diziyle değiştirebilirsiniz. Tüm değerleri 1 olarak başlatın, ardından her satır için yerinde güncelleme yapın: dp[j] += dp[j-1]. i. satır işlendikten sonra dp[j], 2B tablodaki dp[i][j] değerini taşır. Bu, 2B DP problemlerinde yaygın bir optimizasyon örüntüsüdür.
def unique_paths_1d(m, n):
dp = [1] * n # initial row: all 1s
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1] # dp[j] was dp[i-1][j], dp[j-1] is dp[i][j-1]
return dp[n-1]
print(unique_paths_1d(3, 7)) # 28
print(unique_paths_1d(3, 3)) # 6
# Or use math for O(1)
import math
print(math.comb(3+7-2, 3-1)) # 28Benzersiz Yollar II: Engeller
Benzersiz Yollar II (LeetCode 63), ızgaraya engeller (1 ile işaretlenmiş hücreler) ekler. Bir engelin içinden geçen her yol geçersizdir; bu nedenle obstacle[i][j] == 1 ise dp[i][j] = 0 olur. Aksi hâlde yineleme bağıntısı aynıdır: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Başlangıç veya bitiş engelliyse sonuç doğrudan 0 olur. Temel durumları dikkatle başlatın; ilk satırda veya ilk sütunda bir 1 göründükten sonra o satırdaki ya da sütundaki tüm sonraki hücreler 0 olur.
def unique_paths_with_obstacles(obstacle_grid):
m, n = len(obstacle_grid), len(obstacle_grid[0])
dp = [[0] * n for _ in range(m)]
# First row
for j in range(n):
if obstacle_grid[0][j] == 1: break
dp[0][j] = 1
# First column
for i in range(m):
if obstacle_grid[i][0] == 1: break
dp[i][0] = 1
for i in range(1, m):
for j in range(1, n):
if obstacle_grid[i][j] == 0:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
grid = [[0,0,0],[0,1,0],[0,0,0]]
print(unique_paths_with_obstacles(grid)) # 2Minimum Yol Toplamı Problemi
Minimum Yol Toplamı (LeetCode 64) şu soruyu sorar: negatif olmayan tam sayılarla doldurulmuş m×n boyutunda bir ızgara verildiğinde, yalnızca sağa veya aşağı hareket ederek yol üzerindeki tüm sayıların toplamını en aza indiren yolu bulun. Örneğin [[1,3,1],[1,5,1],[4,2,1]] içinde 1→3→1→1→1 yolu toplam 7 verir. DP durumu benzersiz yollar problemindekiyle aynıdır; ancak yineleme bağıntısında toplama yerine minimum kullanılır.
grid = [[1, 3, 1],
[1, 5, 1],
[4, 2, 1]]
# Optimal path: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)
# Values: 1 + 3 + 1 + 1 + 1 = 7
print('Expected minimum path sum:', 7)Minimum Yol Toplamı için DP Uygulaması
dp[i][j] değerini (i,j) hücresine ulaşmanın minimum maliyeti olarak tanımlayın. Temel durum: dp[0][0] = grid[0][0]. İlk satır: dp[0][j] = dp[0][j-1] + grid[0][j] (soldan gelmenin tek yolu). İlk sütun: dp[i][0] = dp[i-1][0] + grid[i][0] (yukarıdan gelmenin tek yolu). Genel durum: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Bu, optimal olma ilkesinin doğrudan uygulanmasıdır.
def min_path_sum(grid):
m, n = len(grid), len(grid[0])
dp = [[0]*n for _ in range(m)]
dp[0][0] = grid[0][0]
for j in range(1, n): # first row
dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1, m): # first column
dp[i][0] = dp[i-1][0] + grid[i][0]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
return dp[m-1][n-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum(grid)) # 7Yerinde Minimum Yol Toplamı
Girdi ızgarasını değiştirmenize izin veriliyorsa, ayrı bir DP tablosu ayırmaktan kaçınmak için ızgarayı yerinde güncelleyebilirsiniz. Bu, girdi dışında kullanılan yardımcı alanı O(1)'e düşürür. Mülakat yapanlar bazen bu optimizasyonu sorar; uygulamadan önce girdiyi değiştirmenize izin verilip verilmediğini netleştirin. İzin verilmiyorsa, 1B dönen dizi yöntemi girdiyi değiştirmeden O(n) alan sağlar.
def min_path_sum_inplace(grid):
m, n = len(grid), len(grid[0])
# Mutate in place
for i in range(m):
for j in range(n):
if i == 0 and j == 0: continue
if i == 0:
grid[i][j] += grid[i][j-1]
elif j == 0:
grid[i][j] += grid[i-1][j]
else:
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[m-1][n-1]
import copy
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_inplace(copy.deepcopy(grid))) # 7Üçgende Minimum Yol Toplamı
Üçgen (LeetCode 120), her adımda aşağıdaki satırdaki bitişik bir sayıya ilerlenen üçgen dizisinde, tepeden tabana minimum yol toplamını bulmayı ister. Aşağıdan yukarıya DP en temiz çözümdür: sondan bir önceki satırdan başlayın ve her hücreye doğrudan altındaki iki hücrenin minimumunu ekleyin. Bu yaklaşım, başlangıç indislerini izleme gereğini ortadan kaldırır ve yanıtı doğal olarak tepeye taşır.
def minimum_total(triangle):
# Bottom-up: start from second-to-last row
dp = triangle[-1][:] # copy of bottom row
for row in range(len(triangle) - 2, -1, -1):
for col in range(len(triangle[row])):
dp[col] = triangle[row][col] + min(dp[col], dp[col+1])
return dp[0]
triangle = [
[2],
[3, 4],
[6, 5, 7],
[4, 1, 8, 3]
]
print(minimum_total(triangle)) # 11 (2+3+5+1)Zindanda Izgara DP'si
Zindan Oyunu (LeetCode 174), negatif (hasar) ve pozitif (iyileşme) hücrelerden oluşan bir ızgaranın sağ alt köşesindeki prensesi kurtarmak için gereken minimum başlangıç canını bulmayı ister. Yalnızca sağa veya aşağı gitmelisiniz. Buradaki püf noktası, DP tablosunu geriye doğru (sağ alttan sol üste) doldurup her hücrede gereken minimum canı hesaplamaktır. Her hücre için: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]). Can her zaman en az 1 olmalıdır.
def calculate_minimum_hp(dungeon):
m, n = len(dungeon), len(dungeon[0])
dp = [[0]*n for _ in range(m)]
# Fill from bottom-right
dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])
for i in range(m-2, -1, -1): # last column
dp[i][n-1] = max(1, dp[i+1][n-1] - dungeon[i][n-1])
for j in range(n-2, -1, -1): # last row
dp[m-1][j] = max(1, dp[m-1][j+1] - dungeon[m-1][j])
for i in range(m-2, -1, -1):
for j in range(n-2, -1, -1):
need = min(dp[i+1][j], dp[i][j+1])
dp[i][j] = max(1, need - dungeon[i][j])
return dp[0][0]
dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
print(calculate_minimum_hp(dungeon)) # 7Izgara DP Problemlerinin Karşılaştırılması
Izgara DP problemleri aynı yapıyı paylaşır; ancak doldurma yönü ve geçiş işlemi bakımından farklılaşır: Benzersiz Yollar toplama kullanır (tüm yolları sayar). Minimum Yol Toplamı minimumu kullanır (en iyi durumu seçer). Zindan Oyunu tabloyu geriye doğru doldurur (ileride gereken canı hesaplar). Yeni bir ızgara DP problemine yaklaşırken kendinize şunları sorun: (1) Her hücre neyi temsil ediyor? (2) Hangi yönde doldurmalıyım? (3) Komşuları hangi işlem birleştiriyor? Bu üç soruyu yanıtlamak çözümün tamamını ortaya çıkarır.
# Summary: Grid DP Patterns
#
# Problem Fill Dir Transition
# Unique Paths top-left dp[i][j] = dp[i-1][j] + dp[i][j-1]
# Unique Paths II top-left same but 0 if obstacle
# Min Path Sum top-left dp[i][j] = grid[i][j] + min(above, left)
# Triangle bottom-up dp[col] = row[col] + min(dp[col], dp[col+1])
# Dungeon bottom-right max(1, min(right, down) - cell)
# Recognise the pattern, write the transition, verify with examples
print('Grid DP summary complete')Izgara DP'si için Karmaşıklık Özeti
Buradaki tüm ızgara DP problemleri O(m×n) zamanda çalışır. Alan, tam bir tablo için O(m×n) değerinden 1B dönen diziyle O(n) değerine, ızgara yerinde değiştirilebildiğinde ise yardımcı alan olarak O(1) değerine kadar düşer. Mülakatlarda O(m×n) çözümünü sunduktan sonra O(n) alan optimizasyonundan da bahsedin; bu, ödünleşimlerin farkında olduğunuzu gösterir. Tüm problemlerde, benzersiz yollar için matematiksel formül gibi açgözlü bir kısayol bulunup bulunmadığını da değerlendirin.
# O(n) space version of Min Path Sum
def min_path_sum_1d(grid):
m, n = len(grid), len(grid[0])
dp = [float('inf')] * n
dp[0] = 0
for i in range(m):
dp[0] += grid[i][0] # first column: only from above
for j in range(1, n):
dp[j] = grid[i][j] + min(dp[j], dp[j-1])
return dp[n-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_1d(grid)) # 7Hızlı Kontrol
Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatına Hazırlık kavramlarını anlayıp anlamadığınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: Benzersiz Yollar, dp[i][j] = dp[i-1][j] + dp[i][j-1] formülüyle bir 2B tablo doldurur ve kombinatorik yöntemlerle O(1) zamanda hesaplanabilir, Minimum Yol Toplamı aynı yapıyı kullanır; ancak en iyi yol maliyeti için toplama yerine min kullanır ve tüm ızgara DP problemleri her hücre için bir durum tanımlama ve bir geçiş işleci (toplam, min, max) seçme örüntüsünü paylaşır. Sırada, iki dizi üzerinde 2B DP kullanarak En Uzun Ortak Alt Diziyi inceleyeceğiz.
Sıkça Sorulan Sorular
“Izgaralarda Benzersiz Yollar ve Minimum Yol Toplamı” dersi ücretsiz mi?
Evet — “Izgaralarda Benzersiz Yollar ve Minimum Yol Toplamı” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“Izgaralarda Benzersiz Yollar ve Minimum Yol Toplamı” dersinde ne öğreneceğim?
Engelli ve engelsiz benzersiz yollar için iki boyutlu DP tablosunu doldurun, ardından bunu bir yol üzerindeki değerlerin toplamını en aza indirecek şekilde uyarlayın. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 1. dersidir.
“Izgaralarda Benzersiz Yollar ve Minimum Yol Toplamı” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Izgaralarda Benzersiz Yollar ve Minimum Yol Toplamı
- En Uzun Ortak Alt Dizi
- Düzenleme Uzaklığı (Levenshtein)
- İki Boyutlu DP için Alan Optimizasyonu