Tablolamayla Aşağıdan Yukarı DP
Yukarıdan aşağı çözümleri yinelemeli DP tablolarına dönüştürün; yalnızca son birkaç girdinin gerektiği durumlarda alanı O(n)’den O(1)’e düşürün.
Tablolamayla Aşağıdan Yukarı DP, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 3. 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.
Aşağıdan Yukarıya DP: Tablolama Yaklaşımı
Aşağıdan yukarıya DP (tablolama), en küçük alt problemlerden başlayıp sonuca doğru ilerleyerek alt problem sonuçlarının bulunduğu bir tabloyu doldurur. Aşağı doğru özyineleme yapıp dönüş yolunda önbelleğe almak yerine, hesaplamaları temelden başlayarak yinelemeli biçimde yaparsınız. Tablo genellikle 1B veya 2B bir dizidir ve her hücre daha önce doldurulmuş hücrelerden yararlanılarak hesaplanır. Bu yaklaşım özyinelemeyi tamamen ortadan kaldırır — çağrı yığını yoktur, özyineleme sınırı yoktur ve önbellek yerelliği daha iyidir.
# Converting top-down to bottom-up:
# Top-down: start at fib(n), recurse to smaller, cache
# Bottom-up: start at fib(0), fill table to fib(n)
# Key question for bottom-up:
# 'In what order do I fill the table so that when I compute dp[i],
# all values dp[i] depends on are already filled?'
# For Fibonacci: dp[i] needs dp[i-1] and dp[i-2]
# Fill order: i = 2, 3, 4, ..., n (left to right)
print('Bottom-up: fill small sub-problems first, build to answer')Aşağıdan Yukarıya Fibonacci
Aşağıdan yukarıya Fibonacci, dp[0..n] aralığını soldan sağa doldurur. dp[i] = dp[i-1] + dp[i-2] bağıntısı i >= 2 için geçerlidir. Temel durumlar olan dp[0] = 0 ve dp[1] = 1 doğrudan dizide saklanır. Zaman karmaşıklığı O(n), tüm tablo için bellek karmaşıklığı O(n)'dir. dp[i] değerinin yalnızca son iki değere bağlı olduğunu gördüğünüzde, iki değişken kullanarak bellek kullanımını O(1)'e düşürebilirsiniz — bu, bellek kullanımını optimize etme adımıdır.
def fib_bottom_up(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0] = 0 # base case
dp[1] = 1 # base case
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print([fib_bottom_up(i) for i in range(10)])
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
# Space-optimised to O(1):
def fib_optimised(n):
if n <= 1: return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
print(fib_optimised(50)) # 12586269025Aşağıdan Yukarıya Madeni Para Değişimi
Madeni para değişimi için aşağıdan yukarıya tablo dp[0..amount] aralığıdır; dp[i] = amount i'yi oluşturmak için gereken minimum madeni para sayısıdır. dp[0] = 0'ı (sıfır miktar için sıfır madeni para) ve dp[1..amount] değerlerini sonsuz olarak başlatın. 1'den hedefe kadar her miktar i için her madeni parayı deneyin: i >= coin ise dp[i] = min(dp[i], 1 + dp[i - coin]) olur. Sonuç dp[amount] değeridir; bu değer hâlâ sonsuzsa -1 döndürülür.
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # base case: 0 coins for amount 0
for i in range(1, amount + 1):
for coin in coins:
if i >= coin: # can use this coin
dp[i] = min(dp[i], 1 + dp[i - coin])
return dp[amount] if dp[amount] != float('inf') else -1
print(coin_change([1, 5, 6, 9], 11)) # 2: (5+6)
print(coin_change([2], 3)) # -1: impossible
print(coin_change([1, 2, 5], 11)) # 3: 5+5+1
print(coin_change([186, 419, 83, 408], 6249)) # 20Doldurma Sırası: Kritik Kavrayış
Doldurma sırası, aşağıdan yukarıya DP'nin özüdür. Herhangi bir dp[i] durumu için, bağlı olduğu tüm durumlar önce hesaplanmış olmalıdır. dp[i] değerinin dp[i-1] ve dp[i-2] değerlerine bağlı olduğu 1B DP'de soldan sağa doldurun. dp[i][j] değerinin dp[i-1][j] ve dp[i][j-1] değerlerine bağlı olduğu 2B DP'de tabloyu satır satır doldurun (yukarıdan aşağıya, soldan sağa). Doldurma sırasını doğrulamak için kodlamadan önce her zaman bağımlılık oklarını çizin.
# Fill order examples:
# 1D: dp[i] = f(dp[i-1], dp[i-2])
# Arrows point LEFT: fill LEFT TO RIGHT
# i: 0 -> 1 -> 2 -> ... -> n
# 2D: dp[i][j] = f(dp[i-1][j], dp[i][j-1])
# Arrows point LEFT and UP: fill TOP-LEFT TO BOTTOM-RIGHT
# Fill row 0 first, then row 1, etc.
# 2D reversed: dp[i][j] = f(dp[i+1][j], dp[i][j+1])
# Arrows point RIGHT and DOWN: fill BOTTOM-RIGHT TO TOP-LEFT
# Used in interval DP and some string problems
print('Draw dependencies first, then determine fill order')Aşağıdan Yukarıya LCS: 2B Tablo
En Uzun Ortak Alt Dizi için aşağıdan yukarıya tablo (m+1) × (n+1) boyutundadır; dp[i][j] = s1[:i] ve s2[:j] dizelerinin LCS'sidir. Temel durumlar: dp[0][j] = dp[i][0] = 0'dır (boş dizenin herhangi bir dizeyle LCS'si 0'dır). Tabloyu satır satır doldurun: s1[i-1] == s2[j-1] ise dp[i][j] = 1 + dp[i-1][j-1]; aksi durumda dp[i][j] = max(dp[i-1][j], dp[i][j-1]) olur. Sonuç dp[m][n] değeridir.
def lcs_bottom_up(s1, s2):
m, n = len(s1), len(s2)
# (m+1) x (n+1) table, initialised to 0
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]: # characters match
dp[i][j] = 1 + dp[i-1][j-1]
else: # skip one character
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
print(lcs_bottom_up('abcde', 'ace')) # 3
print(lcs_bottom_up('ABCBDAB', 'BDCAB')) # 4: 'BCAB' or 'BDAB'Bellek Kullanımını Optimize Etme: Döner Dizi
Birçok 2B DP tablosu, dp[i][j] değerinin yalnızca mevcut satıra ve önceki satıra bağlı olduğu gözlemlenerek 1B'ye (veya 2 satıra) indirgenebilir. prev ve curr olmak üzere iki dizi tutun veya tek bir diziyi doğru sırayla güncelleyin. LCS için dp[i][j] değeri dp[i-1][j], dp[i][j-1] ve dp[i-1][j-1] değerlerine bağlıdır; yalnızca önceki satırı tutmak yeterlidir.
def lcs_space_optimised(s1, s2):
m, n = len(s1), len(s2)
# Keep only one row (previous row state)
prev = [0] * (n + 1)
for i in range(1, m + 1):
curr = [0] * (n + 1)
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
curr[j] = 1 + prev[j-1] # dp[i-1][j-1]
else:
curr[j] = max(prev[j], curr[j-1]) # dp[i-1][j] and dp[i][j-1]
prev = curr
return prev[n]
print(lcs_space_optimised('abcde', 'ace')) # 3
# Space: O(n) instead of O(mn)Aşağıdan Yukarıya Ev Soyguncusu
Ev soyguncusu probleminde aşağıdan yukarıya yaklaşım, dp[0..n-1] aralığını doldurur; dp[i] = 0'dan i'ye kadar olan evleri soyarak elde edilebilecek maksimum kârdır. dp[0] = nums[0], dp[1] = max(nums[0], nums[1]) ve i >= 2 için dp[i] = max(dp[i-1], dp[i-2] + nums[i]) olur. dp[i] yalnızca son iki değere bağlı olduğundan, bu yapı iki değişken kullanılarak hemen O(1) belleğe indirgenebilir — iki adımlı bağımlılıklara sahip 1B DP için yaygın bir örüntüdür.
def rob_bottom_up(nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
# Full table version: O(n) space
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1]
def rob_optimised(nums):
# O(1) space: only need last two values
if not nums: return 0
if len(nums) == 1: return nums[0]
prev2, prev1 = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)):
prev2, prev1 = prev1, max(prev1, prev2 + nums[i])
return prev1
print(rob_optimised([2, 7, 9, 3, 1])) # 12Bir Izgarada Minimum Yol Toplamı
Minimum Yol Toplamı (LeetCode #64): yalnızca sağa veya aşağı hareket ederek sol üstten sağ alta giden ve değerler toplamını en aza indiren bir yol bulun. 2B DP'de dp[i][j] = (i,j) hücresine ulaşmak için gereken minimum toplamdır. dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Soldan sağa ve yukarıdan aşağıya doldurun. Temel durum: dp[0][0] = grid[0][0]; ilk satır yalnızca sağa, ilk sütun ise yalnızca aşağı hareket edilerek doldurulur.
def min_path_sum(grid):
rows, cols = len(grid), len(grid[0])
dp = [[0] * cols for _ in range(rows)]
dp[0][0] = grid[0][0]
# Fill first row (can only come from left)
for c in range(1, cols):
dp[0][c] = dp[0][c-1] + grid[0][c]
# Fill first column (can only come from above)
for r in range(1, rows):
dp[r][0] = dp[r-1][0] + grid[r][0]
# Fill rest of the table
for r in range(1, rows):
for c in range(1, cols):
dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])
return dp[rows-1][cols-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum(grid)) # 7: 1+3+1+1+1DP Tablosunu Yerinde Değiştirme
Ek bellek kullanımı yasak olduğunda, bazen girdi ızgarasının kendisini DP tablosu olarak değiştirebilirsiniz. Minimum yol toplamı için grid[i][j] değerini o hücreye ulaşmanın minimum maliyetiyle değiştirin. Bu yöntem O(1) ek bellek kullanır ancak girdiyi yok eder — bu ödünleşimi her zaman mülakatçıya açıklayın ve bunun kabul edilebilir olduğunu doğrulayın. Girdinin korunması gerekiyorsa döner dizi yaklaşımını kullanın.
def min_path_sum_inplace(grid):
rows, cols = len(grid), len(grid[0])
# Modify grid in-place (O(1) extra space, destroys input)
for r in range(rows):
for c in range(cols):
if r == 0 and c == 0:
continue # starting cell
elif r == 0:
grid[r][c] += grid[r][c-1] # first row
elif c == 0:
grid[r][c] += grid[r-1][c] # first column
else:
grid[r][c] += min(grid[r-1][c], grid[r][c-1])
return grid[rows-1][cols-1]
import copy
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_inplace(copy.deepcopy(grid))) # 7Madeni Para Değişiminde Yukarıdan Aşağıya ve Aşağıdan Yukarıya Yaklaşımları Karşılaştırma
Her iki yaklaşım da madeni para değişimi problemini en iyi şekilde çözer, ancak pratikte farklılık gösterir. Yukarıdan aşağıya yaklaşımın yazımı daha temizdir ve yalnızca gerçekten erişilebilen alt problemleri hesaplar. Aşağıdan yukarıya yaklaşım, verilen paralarla ulaşılamayanlar (sonsuz olarak kalanlar) da dahil olmak üzere 0'dan hedefe kadar tüm miktarları hesaplar. Seyrek problemlerde (az sayıda erişilebilir durum) yukarıdan aşağıya yaklaşım daha verimlidir; yoğun problemlerde ise aşağıdan yukarıya yaklaşımın ek yükü daha azdır.
import functools
# Top-down: only computes reachable amounts
def coin_change_top(coins, amount):
@functools.lru_cache(maxsize=None)
def dp(rem):
if rem == 0: return 0
if rem < 0: return float('inf')
return 1 + min(dp(rem - c) for c in coins)
r = dp(amount)
return r if r != float('inf') else -1
# Bottom-up: computes all amounts 0 to target
def coin_change_bottom(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for c in coins:
if i >= c: dp[i] = min(dp[i], 1 + dp[i-c])
return dp[amount] if dp[amount] != float('inf') else -1
print(coin_change_top([1,5,6,9], 11)) # 2
print(coin_change_bottom([1,5,6,9], 11)) # 2Benzersiz Yollar: Klasik 2B DP
Benzersiz Yollar (LeetCode #62), yalnızca sağa veya aşağıya ilerleyerek m×n boyutundaki bir ızgaranın sol üst köşesinden sağ alt köşesine kaç farklı yolla gidilebileceğini hesaplar. Bağıntı basittir: dp[i][j] = dp[i-1][j] + dp[i][j-1] — yukarıdan gelen yollar artı soldan gelen yollar. Temel durumlarda, ilk satırın ve ilk sütunun tamamında tam olarak 1 yol bulunur (ilerlemek için yalnızca bir yön vardır). Bu 2B DP, O(mn) time içinde doldurulur ve kayan bir satır kullanılarak alan karmaşıklığı O(n)'e düşürülebilir.
def unique_paths(m, n):
# dp[i][j] = number of paths to reach cell (i,j)
dp = [[1] * n for _ in range(m)]
# Base: first row and first column are all 1
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, 2)) # 3
# O(n) space rolling row:
def unique_paths_opt(m, n):
row = [1] * n
for _ in range(1, m):
for j in range(1, n):
row[j] += row[j-1]
return row[n-1]
print(unique_paths_opt(3, 7)) # 28Hızlı Kontrol
Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını anlayıp anlamadığınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: tablolama kullanan aşağıdan yukarıya DP ve bağımlılık oklarından doldurma sırasını belirleme, kayan dizilerle bellek optimizasyonu (O(mn)'den O(n)'e) ve iki değişkenle izleme (O(n)'den O(1)'e) ve Fibonacci, madeni para değişimi, LCS, ev soyguncusu ve minimum yol toplamı problemlerinin aşağıdan yukarıya uygulamaları. Sırada, madeni para değişimi ve minimum maliyetli merdiven problemlerini baştan sona çözeceğiz.
Sıkça Sorulan Sorular
“Tablolamayla Aşağıdan Yukarı DP” dersi ücretsiz mi?
Evet — “Tablolamayla Aşağıdan Yukarı DP” 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.
“Tablolamayla Aşağıdan Yukarı DP” dersinde ne öğreneceğim?
Yukarıdan aşağı çözümleri yinelemeli DP tablolarına dönüştürün; yalnızca son birkaç girdinin gerektiği durumlarda alanı O(n)’den O(1)’e düşürü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 3. dersidir.
“Tablolamayla Aşağıdan Yukarı DP” 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
- DP’yi Tanıma: Çakışan Alt Problemler
- Not Almayla Yukarıdan Aşağı DP
- Tablolamayla Aşağıdan Yukarı DP
- Madeni Para Değişimi ve Minimum Maliyetli Merdiven