Algorithmuspro

Dynamische Programmierung: Treppensteigen

Zähle die Wege eine Treppe hinauf mit Schritten von 1 oder 2 Stufen, aufgebaut aus kleineren Antworten.

Zeit: O(n)
Speicher: O(n)

// Schritt für Schritt

Schritt 1 / 8

1function climbStairs(n) {2  const dp = new Array(n + 1).fill(0);3  dp[0] = 1;4  dp[1] = 1;5  for (let i = 2; i <= n; i++) {6    dp[i] = dp[i - 1] + dp[i - 2];7  }8  return dp[n];9}

n: = 6

Lege ein Array dp an, in dem dp[i] die Anzahl der Wege zu Stufe i speichert.

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

Um auf Stufe i zu landen, kam dein letzter Schritt von Stufe i − 1 oder von Stufe i − 2. Die Wege zu Stufe i sind also die Wege zu i − 1 plus die Wege zu i − 2. Statt diese per Rekursion immer neu zu berechnen, speicherst du jede Antwort in einem Array und füllst es von unten nach oben. Jeder Wert wird einmal berechnet: O(n) Zeit und O(n) Speicher. Es ist die Fibonacci-Rekursion ohne die doppelte Arbeit.

Dieses Muster erkennen üben →