Stitælling i et gitter

Du starter øverst til venstre i et gitter og vil til nederst til højre. Hvert skridt går enten til højre eller ned. Hvor mange forskellige stier findes der?

Hver celle kan nås fra cellen ovenfor eller cellen til venstre. Dette overlap er præcis grunden til, at det er et DP-problem.

Lad dp[i][j] være antallet af måder at nå celle (i, j) fra starten på. At navngive tilstanden tydeligt er halvdelen af arbejdet.

Du kommer kun fra oven eller fra venstre, så antallet er deres sum. Det er denne overgang, der driver hele tabellen.

Startcellen kan nås på præcis én måde: ved ikke at gøre noget. Derfor er dp[0][0] 1, før du udfylder noget andet.

Celler i den øverste række eller venstre kolonne har én lige rute. Deres antal er altid 1, fordi den ene nabo ligger uden for gitteret.

Lav en tabel på m gange n, der er udfyldt med nuller. Når størrelsen fastlægges på forhånd, bliver din indeksering enkel, og du undgår overraskelser.

Gå gennem rækkerne og derefter kolonnerne, fra top til bund og fra venstre mod højre. Denne rækkefølge sikrer, at begge naboer er klar, før du bruger dem.

Efter udfyldningen ligger antallet af stier i den sidste celle. Svaret er dp[m-1][n-1], det nederste højre hjørne.

Hver række har kun brug for rækken ovenfor, så du kan beholde en enkelt række og opdatere den på stedet. Det reducerer hukommelsesforbruget til O(n).

Uden blokeringer er svaret en binomialkoefficient: vælg, hvilke af de samlede skridt der går nedad. DP er stadig bedst, når der opstår forhindringer.

Definér dp som antallet af stier til en celle, sæt dp[0][0] til 1, og læg cellen ovenfor sammen med cellen til venstre. Hjørnet indeholder dit svar. 🧭