DP tablosu
- Algoritmalar kursu
- İleri seviye
- Ders 22/56
- 4 dk
Matris zinciri için DP tablosu kurmayı öğrenirsin.
DP tablosu
İki boyutlu m[i][j] tablosu, i'den j'ye matris çarpımının en düşük maliyetini tutar. Köşegen m[i][i] = 0 çünkü tek matrisin çarpımı yoktur.
Tablo, alt problemleri çözüp sonuçları üst problemlerde kullanır. Bu, dinamik programlamanın temelidir.
Tablo boyutu
n matris için tablo n × n boyutundadır. Başlangıçta tüm değerler sıfır olur; yalnızca köşegen değil tüm hücreler sıfırlanır.
Daha sonra alt problemler çözülerek tablo doldurulur. Önce kısa zincirler, sonra uzun zincirler hesaplanır.
Uygulama init_table fonksiyonu
init_table(n) yaz. n×n sıfır matrisini döndür. print(init_table(4)) ile yazdır.
Başlangıç kodu
def init_table(n):
# n×n sıfır matrisini döndürÖrnek çözüm
def init_table(n):
# n×n sıfır matrisini döndür
return [[0] * n for _ in range(n)]
print(init_table(4))Beklenen çıktı
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Köşegen değeri
m[i][i] = ____m[i][i] = 0Açıklama: 0 doğru.
2 4 matris için tablo boyutu nedir?
- 3×3
- 2×2 Doğru cevap
- 4×4
- 5×5
Açıklama: 3 matris için 4 boyut olduğundan tablo 4×4'tür.
3 DP tablosu: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
m[i][i] |
0 |
m[1][2] |
6000 |
m[2][3] |
24000 |
m[1][3] |
18000 |