Algorithmuspro

Dynamische Programmierung: Wege im Raster

Zähle die Wege durch ein Raster, die sich nur nach rechts oder unten bewegen.

Zeit: O(n·m)
Speicher: O(n·m)

// Schritt für Schritt

Schritt 1 / 8

1function uniquePaths(m, n) {2  const dp = Array.from({ length: m }, () => new Array(n).fill(1));3  for (let r = 1; r < m; r++) {4    for (let c = 1; c < n; c++) {5      dp[r][c] = dp[r - 1][c] + dp[r][c - 1];6    }7  }8  return dp[m - 1][n - 1];9}

	0	1	2	3
0	1	1	1	1
1	1
2	1

Lege eine 3 × 4-Tabelle an. Jede Zelle in der obersten Zeile und der linken Spalte hat genau 1 Weg.

Tipp: Mit den Pfeiltasten durch die Schritte gehen.

// pro-lektion

Den ganzen Durchlauf freischalten

Diese Lektion ist Teil von Pro. Pro schaltet jeden Schritt jeder Lektion frei, dazu Muster-Übungen und Fortschrittsauswertungen.

Preise ansehen

So funktioniert es

Eine Zelle kannst du nur von der Zelle darüber oder der Zelle links davon betreten. Die Wege zu einer Zelle sind also die Wege zur Zelle darüber plus die Wege zur Zelle links. Jede Zelle in der obersten Zeile und der linken Spalte hat genau einen Weg. Fülle die Tabelle Zeile für Zeile, und die Zelle unten rechts enthält die Antwort. Jede Zelle wird einmal berechnet: O(n·m) Zeit und Speicher.

Dieses Muster erkennen üben →