Unique Paths

Robotun sağ alt hücreye yaptığı son hareketi düşünün. Ya üstteki hücreden aşağıya ya da soldaki hücreden sağa geldi; ikisini birden yapmadı. Dolayısıyla m × n boyutundaki bir ızgaradaki yollar, bir satır daha kısa olan ızgaradaki yolların, uniquePaths(m-1, n), toplamı ile bir sütun daha dar olan ızgaradaki yolların, uniquePaths(m, n-1), toplamıdır.

Özyineleme, robotun yalnızca dümdüz ilerleyebildiği tek satırlı veya tek sütunlu bir ızgarada durur; bu durumda tam olarak 1 yol vardır. Her yol iki hareketten biriyle sona erdiğinden, her yol bir kez sayılır ve toplam doğrudur.

Yavaştır; çünkü her yol 1 döndüren bir temel duruma ulaşır, dolayısıyla çağrıların sayısı en az yanıtın kendisi kadardır. 17 × 17 boyutundaki bir ızgara 600 milyondan fazla çağrı gerektirir ve testlerde yanıtlar yaklaşık 1.6 × 10^9 değerine kadar çıkar. Aynı küçük ızgaralar birçok kez hesaplanır: (m-1, n-1) bu ızgaranın iki ebeveyninin her birinden bir kez erişilir ve aşağı indikçe tekrarlar katlanarak artar.

Özyineleme aynı hücreleri tekrar tekrar sorgular ve yalnızca m × n hücre vardır. İhtiyacınız olan hücrelerin her zaman hazır olacağı bir sırayla, her hücreye giden yolları bir kez sayın.

Durum: paths[r][c], sol üst hücreden r. satır, c. sütuna giden yolların sayısıdır. Özyineleme bağıntısı: paths[r][c] = paths[r-1][c] + paths[r][c-1]; yukarıdan gelen yollar ile soldan gelen yolların toplamı. Taban durumları: üst satırdaki ve sol sütundaki her hücreye giden 1 yol vardır; bu, düz bir çizgidir. Sıra: satır satır, soldan sağa; böylece ihtiyaç duymadan önce üstteki ve soldaki hücreler doldurulmuş olur.

m = 3 ve n = 4 için satırlar önce 1 1 1 1, sonra 1 2 3 4, ardından 1 3 6 10 olur ve yanıt son hücredeki 10'dur.

Şimdi doldurma işleminin neleri okuduğuna bakın: yalnızca üstteki satırı ve doldurduğunuz satırı. Bu yüzden tek bir satır tutun. row[c] değerini güncellemeden önce, bu değer hâlâ üstteki satırın sayısını tutar ve row[c-1] soldaki yeni sayıyı zaten tutar; dolayısıyla row[c] += row[c-1] tüm özyineleme bağıntısını ifade eder. Çalışma süresi O(m × n) olarak kalır ve bellek kullanımı O(m × n) değerinden O(n) değerine düşer.

Her yol tam olarak m-1 aşağı ve n-1 sağa hareket, toplamda m+n-2 hareket yapar; bu hareketler herhangi bir sırada olabilir. Her sıralama geçerli bir yoldur: robot hiçbir zaman m-1'den fazla aşağı veya n-1'den fazla sağa hareket etmez, dolayısıyla ızgaranın dışına çıkmaz. Bu nedenle bir yol, m+n-2 hareketten hangilerinin aşağı gideceğini seçmekle aynı şeydir ve cevap binom katsayısı C(m+n-2, m-1) olur.

Önceki yaklaşımdaki tablo, yan çevrilmiş Pascal üçgenidir; bu yüzden ikisi aynı sonucu verir. Katsayıyı devasa faktöriyeller hesaplamadan bulmak için, çarpımı her seferinde bir çarpan ekleyerek oluştur. N = m+n-2 ve k = min(m, n)-1 iken, i değeri 1'den k'ye kadar giderken N-k+i ile çarp ve ardından i'ye böl. i adımından sonra biriken değer C(N-k+i, i) olur; bu bir tam sayıdır, dolayısıyla her bölme tam sonuç verir.

m = 3 ve n = 4 için: N = 5, k = 2 olur ve değer önce 1 × 4 / 1 = 4, ardından 4 × 5 / 2 = 10 şeklinde ilerler. Daha kısa kenarı seçmek döngünün 99 adım veya daha az sürmesini sağlar. Son bölmeden önceki çarpım, cevap değerinin k katıdır. 17 × 17 boyutundaki bir ızgarada bu, 16 × 601,080,390, yani yaklaşık 9.6 × 10^9 eder; bu değer 32 bitlik aralığı aşar, bu yüzden 64 bitlik bir tamsayı kullan.