Unique Paths

Pomyśl o ostatnim ruchu robota do komórki w prawym dolnym rogu. Robot dotarł do niej albo z góry, z komórki powyżej, albo z prawej, z komórki po lewej — nigdy z obu kierunków. Zatem ścieżki przez siatkę m × n to ścieżki przez siatkę o jeden wiersz krótszą, uniquePaths(m-1, n), oraz ścieżki przez siatkę o jedną kolumnę węższą, uniquePaths(m, n-1).

Rekurencja kończy się na siatce z jednym wierszem lub jedną kolumną, gdzie robot może poruszać się tylko prosto, więc istnieje dokładnie 1 ścieżka. Każda ścieżka kończy się jednym z dwóch ruchów, dlatego każda jest liczona raz, a suma jest poprawna.

Działa to wolno, ponieważ każda ścieżka kończy się przypadkiem bazowym, który zwraca 1, więc liczba wywołań jest co najmniej równa samej odpowiedzi. Siatka 17 × 17 wymaga ponad 600 milionów wywołań, a testy sięgają odpowiedzi bliskich 1.6 × 10^9. Te same mniejsze siatki są obliczane wiele razy: do (m-1, n-1) dociera się raz z każdego z dwóch węzłów nadrzędnych, a liczba powtórzeń rośnie w miarę schodzenia w dół.

Rekurencja wielokrotnie pyta o te same komórki, a jest ich tylko m × n. Oblicz liczbę ścieżek do każdej komórki tylko raz, w takiej kolejności, by komórki, których potrzebujesz, były już zawsze gotowe.

Stan: paths[r][c] to liczba ścieżek od komórki w lewym górnym rogu do wiersza r, kolumny c. Rekurencja: paths[r][c] = paths[r-1][c] + paths[r][c-1], czyli liczba ścieżek prowadzących z góry plus liczba ścieżek prowadzących z lewej. Przypadki bazowe: każda komórka w górnym wierszu i w lewej kolumnie ma 1 ścieżkę — prostą linię. Kolejność: wiersz po wierszu, od lewej do prawej, tak aby komórka powyżej i komórka po lewej były wypełnione, zanim będą potrzebne.

Dla m = 3 i n = 4 wiersze to 1 1 1 1, następnie 1 2 3 4, a potem 1 3 6 10. Odpowiedzią jest ostatnia komórka: 10.

Przyjrzyj się teraz temu, co odczytuje proces wypełniania: tylko wiersz powyżej i wiersz, który wypełniasz. Wystarczy więc przechowywać jeden wiersz. Zanim zaktualizujesz row[c], nadal zawiera on liczbę z wiersza powyżej, a row[c-1] zawiera już nową liczbę po lewej, więc row[c] += row[c-1] stanowi całą rekurencję. Czas działania pozostaje równy O(m × n), a zużycie pamięci spada z O(m × n) do O(n).

Każda ścieżka składa się z dokładnie m-1 ruchów w dół i n-1 ruchów w prawo, czyli łącznie m+n-2 ruchów w pewnej kolejności. Każda kolejność tworzy poprawną ścieżkę: robot nigdy nie wykonuje więcej niż m-1 ruchów w dół ani n-1 ruchów w prawo, więc nigdy nie opuszcza siatki. Ścieżka jest zatem równoważna wyborowi, które m-1 spośród m+n-2 ruchów prowadzą w dół, a odpowiedzią jest współczynnik dwumianowy C(m+n-2, m-1).

Tabela z poprzedniego podejścia to trójkąt Pascala obrócony na bok, dlatego oba podejścia dają ten sam wynik. Aby obliczyć współczynnik bez ogromnych silni, buduj go po jednym czynniku naraz. Przy N = m+n-2 i k = min(m, n)-1 pomnóż przez N-k+i, a następnie podziel przez i, dla i od 1 do k. Po kroku i bieżąca wartość wynosi C(N-k+i, i), czyli jest liczbą całkowitą, więc każde dzielenie jest dokładne.

Dla m = 3 i n = 4: N = 5, k = 2, a wartość zmienia się następująco: 1 × 4 / 1 = 4, a następnie 4 × 5 / 2 = 10. Wybór krótszego boku sprawia, że pętla wykonuje najwyżej 99 kroków. Iloczyn przed ostatnim dzieleniem wynosi k razy tyle, co odpowiedź. Dla siatki 17 × 17 jest to 16 × 601,080,390, czyli około 9.6 × 10^9 — wartość przekraczająca zakres 32-bitowy, więc przechowuj ją w 64-bitowej liczbie całkowitej.