Räkna vägar i ett rutnät

Ni börjar längst upp till vänster i ett rutnät och vill ta Er till längst ned till höger. Varje steg går åt höger eller nedåt. Hur många olika vägar finns det?

Varje cell kan nås från cellen ovanför eller från cellen till vänster. Den överlappningen är precis varför detta är ett DP-problem.

Låt dp[i][j] vara antalet sätt att nå cell (i, j) från startpunkten. Att namnge tillståndet tydligt är halva arbetet.

Ni kommer bara från ovan eller från vänster, så antalet är summan av dessa två värden. Det här är den övergång som driver hela tabellen.

Startcellen kan nås på exakt ett sätt: genom att inte göra någonting. Därför är dp[0][0] 1 innan Ni fyller i något annat.

Cellerna i den översta raden eller den vänstra kolumnen har en enda rak väg. Deras antal är alltid 1, eftersom en av grannarna ligger utanför rutnätet.

Skapa en m by n-tabell fylld med nollor. Om Ni bestämmer storleken från början blir indexeringen renare och överraskningar undviks.

Iterera först över rader och sedan över kolumner, uppifrån och ned samt från vänster till höger. Denna ordning garanterar att båda grannarna är klara innan Ni använder dem.

När tabellen är ifylld finns antalet vägar i den sista cellen. Svaret är dp[m-1][n-1], hörnet längst ned till höger.

Varje rad behöver bara raden ovanför, så Ni kan behålla en enda rad och uppdatera den på plats. Det minskar minnesåtgången till O(n).

Utan blockeringar är svaret en binomialkoefficient: välj vilka av det totala antalet steg som ska gå nedåt. DP är fortfarande bäst när hinder dyker upp.

Definiera dp som antalet vägar till en cell, sätt dp[0][0] till 1 och addera cellen ovanför och cellen till vänster. Hörnet innehåller svaret. 🧭