Easy Dynamic Programming
Climbing Stairs
Receives a non-negative integer n, the number of stairs in a staircase, and returns the number of distinct ways to reach the top when each move is either 1 or 2 steps. It computes the answer with bottom-up dynamic programming: the number of ways to reach step k is the sum of the ways to reach the two steps before it (ways(k) = ways(k-1) + ways(k-2)), so it fills that recurrence iteratively from the base cases ways(0) = ways(1) = 1 up to n, using two rolling variables instead of recursion. Returns the single integer ways(n); n ≤ 1 returns 1 directly (a staircase of zero or one step has exactly one trivial way to climb it).
Visualization
- Input
- Result
Algorithm code
// Climbing Stairs — a single pure function. Receives a non-negative integer n
// (the number of stairs) and returns the number of distinct ways to reach the
// top, taking either 1 or 2 steps at a time. Computed via bottom-up dynamic
// programming: ways(n) = ways(n-1) + ways(n-2), built iteratively from the
// base cases in O(n) time and O(1) extra space.
/**
* @param {number} n - number of stairs to climb
* @returns {number} the number of distinct ways to reach the top
*/
export function climbingStairs(n) {
if (n <= 1) return 1;
let prev = 1;
let curr = 1;
for (let step = 2; step <= n; step += 1) {
const next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}FUNCTION climbingStairs(n):
IF n <= 1:
RETURN 1
prev ← 1
curr ← 1
FOR step FROM 2 TO n:
next ← prev + curr
prev ← curr
curr ← next
RETURN curr