Climbing Stairs

Problem Statement

Solution 1: Recursive with Memoization

function climbStairsMemoization(n) {
    const memo = {};
    function climb(n) {
        if (n <= 1) return 1;
        if (memo[n]) return memo[n];
        memo[n] = climb(n - 1) + climb(n - 2);
        return memo[n];
    }
    return climb(n);
} 

const n1 = 2;
climbStairsMemoization(n1);  //output: 2 

const n2 = 3;
climbStairsMemoization(n2);  //output: 3 

Solution 2: Dynamic Programming with a Class

function climbStairsDPClass(n) {
    class Climber {
        constructor(n) {
            this.n = n;
            this.dp = new Array(n + 1).fill(0);
            this.dp[1] = 1;
            this.dp[2] = 2;
        }

        calculateWays() {
            for (let i = 3; i <= this.n; i++) {
                this.dp[i] = this.dp[i - 1] + this.dp[i - 2];
            }
            return this.dp[this.n];
        }
    }

    let climber = new Climber(n);
    return climber.calculateWays();
} 

const n1 = 2;
climbStairsDPClass(n1);  //output: 2 

const n2 = 3;
climbStairsDPClass(n2);  //output: 3 

Solution 3: Depth-First Search (DFS) Approach

function climbStairsDFS(n) {
    function dfs(current) {
        if (current === n) return 1;
        if (current > n) return 0;
        return dfs(current + 1) + dfs(current + 2);
    }
    return dfs(0);
} 

const n1 = 2;
climbStairsDFS(n1);  //output: 2 

const n2 = 3;
climbStairsDFS(n2);  //output: 3 

Solution 4: Dynamic Programming (Tabulation)

function climbStairsTabulation(n) {
    if (n <= 1) return 1;
    const dp = Array(n + 1).fill(0);
    dp[1] = 1;
    dp[2] = 2;
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
} 

const n1 = 2;
climbStairsTabulation(n1);  //output: 2 

const n2 = 3;
climbStairsTabulation(n2);  //output: 3 

Solution 5: Dynamic Programming (Space Optimization)

function climbStairsSpaceOptimized(n) {
    if (n <= 1) return 1;
    let a = 1, b = 2;
    for (let i = 3; i <= n; i++) {
        const c = a + b;
        a = b;
        b = c;
    }
    return b;
} 

const n1 = 2;
climbStairsSpaceOptimized(n1);  //output: 2 

const n2 = 3;
climbStairsSpaceOptimized(n2);  //output: 3 

Solution 6: Simple Recursive

function climbStairsRecursive(n) {
    if (n <= 1) return 1;
    return climbStairsRecursive(n - 1) + climbStairsRecursive(n - 2);
} 

const n1 = 2;
climbStairsRecursive(n1);  //output: 2 

const n2 = 3;
climbStairsRecursive(n2);  //output: 3 

Solution 7: Iterative Approach

function climbStairsIterative(n) {
    if (n <= 1) return 1;
    let first = 1, second = 1;
    for (let i = 2; i <= n; i++) {
        const temp = first + second;
        first = second;
        second = temp;
    }
    return second;
} 

const n1 = 2;
climbStairsIterative(n1);  //output: 2 

const n2 = 3;
climbStairsIterative(n2);  //output: 3 

Solution 8: Using a Stack (Depth-First Search)

function climbStairsDFS2(n) {
    function dfs(n) {
        if (n <= 1) return 1;
        return dfs(n - 1) + dfs(n - 2);
    }
    return dfs(n);
} 

const n1 = 2;
climbStairsDFS2(n1);  //output: 2 

const n2 = 3;
climbStairsDFS2(n2);  //output: 3 

Solution 9: Using an Explicit Stack

function climbStairsStack(n) {
    const stack = [n];
    const visited = new Set();
    let result = 0;

    while (stack.length) {
        const current = stack.pop();
        if (current <= 1) {
            result += 1;
            continue;
        }
        if (!visited.has(current)) {
            visited.add(current);
            stack.push(current - 1);
            stack.push(current - 2);
        }
    }
    return result;
} 

const n1 = 2;
climbStairsStack(n1);  //output: 2 

const n2 = 3;
climbStairsStack(n2);  //output: 3 

Solution 10: Using a Queue (Breadth-First Search)

function climbStairsBFS(n) {
    if (n <= 1) return 1;
    let result = 0;
    const queue = [{ steps: n }];

    while (queue.length) {
        const { steps } = queue.shift();
        if (steps === 0) {
            result += 1;
        } else if (steps > 0) {
            queue.push({ steps: steps - 1 });
            queue.push({ steps: steps - 2 });
        }
    }
    return result;
} 

const n1 = 2;
climbStairsBFS(n1);  //output: 2 

const n2 = 3;
climbStairsBFS(n2);  //output: 3 

Solution 11: Using a HashMap for Memoization

function climbStairsHashMap(n) {
    const memo = new Map();
    function countWays(n) {
        if (n <= 1) return 1;
        if (memo.has(n)) return memo.get(n);
        const result = countWays(n - 1) + countWays(n - 2);
        memo.set(n, result);
        return result;
    }
    return countWays(n);
} 

const n1 = 2;
climbStairsHashMap(n1);  //output: 2 

const n2 = 3;
climbStairsHashMap(n2);  //output: 3 

Solution 12: Using an Array-Based Recursion

function climbStairsArrayRecursion(n) {
    const memo = Array(n + 1).fill(0);
    function countWays(n) {
        if (n <= 1) return 1;
        if (memo[n] !== 0) return memo[n];
        memo[n] = countWays(n - 1) + countWays(n - 2);
        return memo[n];
    }
    return countWays(n);
} 

const n1 = 2;
climbStairsArrayRecursion(n1);  //output: 2 

const n2 = 3;
climbStairsArrayRecursion(n2);  //output: 3 

Solution 13: Using Dynamic Programming with Sliding Window

function climbStairsSlidingWindow(n) {
    if (n <= 1) return 1;
    let [a, b] = [1, 1];
    for (let i = 2; i <= n; i++) {
        [a, b] = [b, a + b];
    }
    return b;
} 

const n1 = 2;
climbStairsSlidingWindow(n1);  //output: 2 

const n2 = 3;
climbStairsSlidingWindow(n2);  //output: 3 

Solution 14: Using a Fibonacci Sequence Formula

function climbStairsFibonacciFormula(n) {
    function fibonacci(n) {
        const phi = (1 + Math.sqrt(5)) / 2;
        const psi = (1 - Math.sqrt(5)) / 2;
        return Math.round((Math.pow(phi, n + 1) - Math.pow(psi, n + 1)) / Math.sqrt(5));
    }
    return fibonacci(n);
} 

const n1 = 2;
climbStairsFibonacciFormula(n1);  //output: 2 

const n2 = 3;
climbStairsFibonacciFormula(n2);  //output: 3 

Solution 15: Using a Recursive Generator

function climbStairsUsingGenerator(n) {
    let count = 0;
    for (const _ of climbStairsGenerator(n)) {
        count++;
    }
    return count;
}
function* climbStairsGenerator(n) {
    if (n <= 1) {
        yield 1;
        return;
    }
    yield* climbStairsGenerator(n - 1);
    yield* climbStairsGenerator(n - 2);
} 

const n1 = 2;
climbStairsUsingGenerator(n1);  //output: 2 

const n2 = 3;
climbStairsUsingGenerator(n2);  //output: 3 

Solution 16: Using Permutations

function climbStairsPermutations(n) {
    function countWays(n, k) {
        if (n < 0) return 0;
        if (n === 0) return 1;
        if (k <= 0) return 0;
        return countWays(n - 1, k - 1) + countWays(n - 2, k - 1);
    }
    return countWays(n, n);
} 

const n1 = 2;
climbStairsPermutations(n1);  //output: 2 

const n2 = 3;
climbStairsPermutations(n2);  //output: 3 

Solution 17: Using a Priority Queue

function climbStairsPriorityQueue(n) {
    if (n <= 1) return 1;
    const pq = [{ steps: n, ways: 0 }];
    let result = 0;
    
    while (pq.length) {
        const { steps } = pq.shift();
        if (steps === 0) {
            result += 1;
        } else if (steps > 0) {
            pq.push({ steps: steps - 1 });
            pq.push({ steps: steps - 2 });
        }
    }
    return result;
} 

const n1 = 2;
climbStairsPriorityQueue(n1);  //output: 2 

const n2 = 3;
climbStairsPriorityQueue(n2);  //output: 3 

More Problems Solutions