Zliczanie ścieżek na siatce

Rozpoczynają Państwo w lewym górnym rogu siatki i chcą dotrzeć do prawego dolnego rogu. Każdy krok prowadzi w prawo albo w dół. Ile istnieje różnych ścieżek?

Do każdej komórki można dotrzeć z komórki powyżej albo z komórki po lewej. To nakładanie się podproblemów dokładnie wyjaśnia, dlaczego jest to problem DP.

Niech dp[i][j] oznacza liczbę sposobów dotarcia do komórki (i, j) z punktu początkowego. Jasne nazwanie stanu to połowa sukcesu.

Do komórki można dotrzeć tylko z góry albo z lewej, więc liczba sposobów jest sumą obu wartości. To przejście napędza całą tabelę.

Do komórki początkowej można dotrzeć dokładnie na jeden sposób: nie wykonując żadnego ruchu. Dlatego dp[0][0] ma wartość 1, zanim zostaną wypełnione pozostałe komórki.

Komórki w górnym wierszu lub lewej kolumnie mają jedną prostą trasę. Ich licznik zawsze wynosi 1, ponieważ jeden z sąsiadów leży poza siatką.

Należy utworzyć tabelę m na n wypełnioną zerami. Ustalenie jej rozmiaru z góry pozwala zachować przejrzyste indeksowanie i uniknąć niespodzianek.

Należy iterować najpierw po wierszach, a następnie po kolumnach — od góry do dołu i od lewej do prawej. Taka kolejność gwarantuje, że obaj sąsiedzi są gotowi, zanim zostaną użyci.

Po wypełnieniu tabeli liczba ścieżek znajduje się w ostatniej komórce. Odpowiedzią jest dp[m-1][n-1], czyli prawy dolny róg.

Każdy wiersz potrzebuje tylko wiersza znajdującego się nad nim, dlatego można przechowywać pojedynczy wiersz i aktualizować go w miejscu. Zmniejsza to zużycie pamięci do O(n).

Gdy nie ma przeszkód, odpowiedzią jest współczynnik dwumianowy: należy wybrać, które z wszystkich kroków będą prowadzić w dół. DP nadal sprawdza się lepiej, gdy pojawiają się przeszkody.

Wypełniają Państwo dp[i][j] dla dostępnej komórki wewnętrznej. Który wzór jest poprawny?

Należy zdefiniować dp jako liczbę ścieżek prowadzących do komórki, ustawić dp[0][0] na 1, a następnie dodać wartość z komórki powyżej i z komórki po lewej. W rogu znajduje się odpowiedź. 🧭