Bu problem, A noktasından B noktasına ok yönlerini takip ederek kaç farklı yolla ulaşılabileceğini bulmayı gerektiren bir dinamik programlama (DP) problemidir.
- Adım 1: DP Tablosu Oluşturma
- Adım 2: Başlangıç ve Sınır Koşulları
- Adım 3: Tekrarlama Bağıntısı
- Adım 4: DP Tablosunu Doldurma
Izgaradaki her bir düğüm (köşe) için, A noktasından o düğüme ulaşmanın kaç farklı yolu olduğunu saklayacak bir $dp[i][j]$ tablosu tanımlayalım. Burada $i$ satırı (aşağıdan yukarıya, 0'dan 4'e) ve $j$ sütunu (soldan sağa, 0'dan 4'e) temsil eder. A noktası $ (0,0) $ konumunda, B noktası ise $ (4,4) $ konumundadır.
A noktasından A noktasına ulaşmanın 1 yolu vardır: $dp[0][0] = 1$.
İlk satır ($i=0$) ve ilk sütundaki ($j=0$) düğümlere sadece tek bir yönden (sağa veya yukarı) ulaşılabilir. Bu nedenle, $dp[0][j] = 1$ (sadece sağa hareket) ve $dp[i][0] = 1$ (sadece yukarı hareket) olur.
Diğer tüm düğümler $(i, j)$ için, ok yönleri (sağa, yukarı, çapraz yukarı-sağa) nedeniyle üç farklı yoldan ulaşılabilir. Bu yollar, sırasıyla $(i, j-1)$, $(i-1, j)$ ve $(i-1, j-1)$ düğümlerinden gelir. Dolayısıyla, tekrarlama bağıntısı şu şekildedir:
$$dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]$$
Yukarıdaki kuralları kullanarak 5x5'lik DP tablosunu dolduralım. Tablo, A noktasından (sol alt köşe) her bir düğüme ulaşım yollarını gösterir:
| 1 | 9 | 41 | 129 | 321 |
| 1 | 7 | 25 | 63 | 129 |
| 1 | 5 | 13 | 25 | 41 |
| 1 | 3 | 5 | 7 | 9 |
| 1 | 1 | 1 | 1 | 1 |
B noktası olan $ (4,4) $ konumundaki değer, A noktasından B noktasına ulaşmak için toplam yol sayısını verir.
Bu değer 321'dir.
Cevap D seçeneğidir.