DP tablosu
- Algoritmalar kursu
- İleri seviye
- Ders 10/56
- 4 dk
LCS için iki boyutlu DP tablosu kurmayı öğrenirsin.
DP tablosu
LCS için iki boyutlu bir DP tablosu kurarız. dp[i][j], s1'in ilk i ve s2'nin ilk j karakterinin LCS uzunluğudur.
Tablo (len(s1)+1) × (len(s2)+1) boyutundadır; ilk satır ve sütun sıfırdır.
Her hücre, eşleşme olursa köşegen üstü +1, değilse sol/üstün max'ı olarak doldurulur.
Hücre bağıntısı
Eğer s1[i-1] == s2[j-1] ise dp[i][j] = dp[i-1][j-1] + 1. Değilse dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Bu bağıntı, tabloyu sırayla doldurarak LCS uzunluğunu verir.
Sonuç dp[len(s1)][len(s2)] hücresindedir; tablonun sağ-alt köşesi.
Uygulama LCS uzunluk DP
lcs_len(s1, s2) yaz. DP tablosuyla LCS uzunluğunu bul. print(lcs_len("ABCBDAB", "BDCAB")) ile 4 yazdır.
Başlangıç kodu
def lcs_len(s1, s2):
# LCS uzunluk DPÖrnek çözüm
def lcs_len(s1, s2):
# LCS uzunluk DP
m, n = len(s1), len(s2)
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]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
print(lcs_len("ABCBDAB", "BDCAB"))Beklenen çıktı
4
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Eşleşme bağıntısı
dp[i][j] = dp[i - 1][j - 1] + ____dp[i][j] = dp[i - 1][j - 1] + 1Açıklama: 1 doğru.
2 DP tablosu: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
dp[i][j] |
Hücre |
match |
Eşleşme |
diagonal |
Köşegen |
max |
Büyük |
3 LCS tablosu hangi boyuttadır?
- (m+1) × (n+1) Doğru cevap
- (m-1) × (n-1)
- m + n
- m × n
Açıklama: (m+1) × (n+1).