DP çözümü

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.

Örnek çözümü göster

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()))

Kendini test et

DP çözümü: kavramları eşleştir

dp[0]

0
dp[1]

10
dp[2]

25
dp[3]

55
A'dan D'ye en düşük maliyet kaçtır?
- 60
- 50
- 55
- 30
Cevabı göster

55 — A→C→D yolu 25+30=55 verir.
iç döngü değişkeni
```
for j in ____(i):
```
Cevabı göster
```
for j in range(i):
```

Sıradaki ders: Sonuç yazdır

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler