DP çözümü
- Algoritmalar kursu
- İleri seviye
- Ders 19/56
- 4 dk
En ucuz rotayı DP ile hesaplarsın.
DP tanımı
dp[i], başlangıç şehrinden i'ye gitmenin en düşük maliyetidir. Başlangıçta dp[0] = 0 çünkü başlangıç şehrindeyiz.
Her i için, daha küçük tüm j'lerden gelinen yollar arasından en düşük olanı seçeriz. Bu, optimal alt yapı özelliğidir.
Tekrarlama bağıntısı
DP bağıntısı: dp[i] = min(dp[j] + cost[j][i]) tüm j < i için. Her i için, kendisinden önce gelen tüm şehirleri deneyip en iyisini seçeriz.
Bu formül, çakışan alt problemler özelliğinden yararlanır. Her alt problem yalnızca bir kez hesaplanır.
Uygulama dp_min_cost fonksiyonu
dp_min_cost(cost) yaz. dp dizisini kur, dp[i] = min(dp[j] + cost[j][i]) ile. print(dp_min_cost(init_cost())) ile 55 yazdır.
Başlangıç kodu
def init_cities():
# Şehir listesini döndür
return ['A', 'B', 'C', 'D']
def init_cost():
# Maliyet matrisini döndür
return [[0, 10, 25, 60], [0, 0, 20, 50], [0, 0, 0, 30], [0, 0, 0, 0]]
def dp_min_cost(cost):
# En düşük maliyeti bulÖrnek çözüm
def init_cities():
# Şehir listesini döndür
return ['A', 'B', 'C', 'D']
def init_cost():
# Maliyet matrisini döndür
return [[0, 10, 25, 60], [0, 0, 20, 50], [0, 0, 0, 30], [0, 0, 0, 0]]
def dp_min_cost(cost):
# En düşük maliyeti bul
n = len(cost)
dp = [0] * n
for i in range(1, n):
best = float('inf')
for j in range(i):
cand = dp[j] + cost[j][i]
if cand < best:
best = cand
dp[i] = best
return dp[n - 1]
print(dp_min_cost(init_cost()))Beklenen çıktı
55
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 DP çözümü: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
dp[0] |
0 |
dp[1] |
10 |
dp[2] |
25 |
dp[3] |
55 |
2 A'dan D'ye en düşük maliyet kaçtır?
- 60
- 50
- 55 Doğru cevap
- 30
Açıklama: A→C→D yolu 25+30=55 verir.
3 iç döngü değişkeni
for j in ____(i):for j in range(i):Açıklama: range doğru.