Solution 1 - Recursive (Brute Force)

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. Count the number of distinct ways to climb to the top. This is essentially the Fibonacci sequence: ways(n) = ways(n-1) + ways(n-2).

TimeComplexity: O(2^n)

SpaceComplexity: O(n)

""" 0070.1 - Climbing Stairs - Solution 1 - Recursive (Brute Force) """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def climbStairs(self, n: int) -> int:
        """Climbing Stairs Function"""
        if n <= 2:
            return n
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().climbStairs(2))   # 2
    print(Solution().climbStairs(3))   # 3
    print(Solution().climbStairs(5))   # 8


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

/** 0070.1 - Climbing Stairs - Solution 1 - Recursive (Brute Force) */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class Solution {
    /** Climbing Stairs Function */
    climbStairs(n) {
        if (n <= 2) return n;
        return this.climbStairs(n - 1) + this.climbStairs(n - 2);
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase() {
    /** Test Function */
    const solution = new Solution();
    console.log(solution.climbStairs(2)); // 2
    console.log(solution.climbStairs(3)); // 3
    console.log(solution.climbStairs(5)); // 8
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

/** 0070.1 - Climbing Stairs - Solution 1 - Recursive (Brute Force) */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class Solution {
    /** Climbing Stairs Function */
    climbStairs(n: number): number {
        if (n <= 2) return n;
        return this.climbStairs(n - 1) + this.climbStairs(n - 2);
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase(): void {
    /** Test Function */
    const solution = new Solution();
    console.log(solution.climbStairs(2)); // 2
    console.log(solution.climbStairs(3)); // 3
    console.log(solution.climbStairs(5)); // 8
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

// 0070.1 - Climbing Stairs - Solution 1 - Recursive (Brute Force)

package main

/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
import "fmt"

/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
func climbStairs(n int) int {
	if n <= 2 {
		return n
	}
	return climbStairs(n-1) + climbStairs(n-2)
}

func testcase() {
	// Test Function
	fmt.Println(climbStairs(2)) // 2
	fmt.Println(climbStairs(3)) // 3
	fmt.Println(climbStairs(5)) // 8
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
func main() {
	testcase()
}

// 0070.1 - Climbing Stairs - Solution 1 - Recursive (Brute Force)

/////////////////////////////////////////////////////////////////////////////////////
// Structs
/////////////////////////////////////////////////////////////////////////////////////
struct Solution;

/////////////////////////////////////////////////////////////////////////////////////
// Implementations
/////////////////////////////////////////////////////////////////////////////////////
impl Solution {
    /// Climbing Stairs Function
    pub fn climb_stairs(n: i32) -> i32 {
        if n <= 2 {
            return n;
        }
        Solution::climb_stairs(n - 1) + Solution::climb_stairs(n - 2)
    }
}

fn main() {
    println!("{}", Solution::climb_stairs(5)); // 8
}

Solution 2 - Memoization (Top-Down DP)

Same recursive approach but we cache previously computed results in a dictionary to avoid redundant calculations. Each subproblem is solved only once.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0070.2 - Climbing Stairs - Solution 2 - Memoization (Top-Down DP) """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def climbStairs(self, n: int) -> int:
        """Climbing Stairs Function"""
        memo = {}

        def helper(k: int) -> int:
            if k <= 2:
                return k
            if k in memo:
                return memo[k]
            memo[k] = helper(k - 1) + helper(k - 2)
            return memo[k]

        return helper(n)


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().climbStairs(2))   # 2
    print(Solution().climbStairs(3))   # 3
    print(Solution().climbStairs(5))   # 8


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

/** 0070.2 - Climbing Stairs - Solution 2 - Memoization (Top-Down DP) */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class Solution {
    /** Climbing Stairs Function */
    climbStairs(n) {
        const memo = new Map();

        const helper = (k) => {
            if (k <= 2) return k;
            if (memo.has(k)) return memo.get(k);
            const v = helper(k - 1) + helper(k - 2);
            memo.set(k, v);
            return v;
        };

        return helper(n);
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase() {
    /** Test Function */
    const solution = new Solution();
    console.log(solution.climbStairs(2)); // 2
    console.log(solution.climbStairs(3)); // 3
    console.log(solution.climbStairs(5)); // 8
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

/** 0070.2 - Climbing Stairs - Solution 2 - Memoization (Top-Down DP) */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class Solution {
    /** Climbing Stairs Function */
    climbStairs(n: number): number {
        const memo: Map<number, number> = new Map();

        const helper = (k: number): number => {
            if (k <= 2) return k;
            const cached = memo.get(k);
            if (cached !== undefined) return cached;

            const v: number = helper(k - 1) + helper(k - 2);
            memo.set(k, v);
            return v;
        };

        return helper(n);
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase(): void {
    /** Test Function */
    const solution = new Solution();
    console.log(solution.climbStairs(2)); // 2
    console.log(solution.climbStairs(3)); // 3
    console.log(solution.climbStairs(5)); // 8
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

// 0070.2 - Climbing Stairs - Solution 2 - Memoization (Top-Down DP)

package main

/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
import "fmt"

/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
func climbStairsMemo(n int) int {
	memo := map[int]int{}

	var helper func(int) int
	helper = func(k int) int {
		if k <= 2 {
			return k
		}
		if v, ok := memo[k]; ok {
			return v
		}
		memo[k] = helper(k-1) + helper(k-2)
		return memo[k]
	}

	return helper(n)
}

func testcase() {
	// Test Function
	fmt.Println(climbStairsMemo(2)) // 2
	fmt.Println(climbStairsMemo(3)) // 3
	fmt.Println(climbStairsMemo(5)) // 8
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
func main() {
	testcase()
}

// 0070.2 - Climbing Stairs - Solution 2 - Memoization (Top-Down DP)

use std::collections::HashMap;

struct Solution;

impl Solution {
    /// Climbing Stairs Function
    pub fn climb_stairs(n: i32) -> i32 {
        fn helper(k: i32, memo: &mut HashMap<i32, i32>) -> i32 {
            if k <= 2 {
                return k;
            }
            if let Some(&v) = memo.get(&k) {
                return v;
            }
            let v = helper(k - 1, memo) + helper(k - 2, memo);
            memo.insert(k, v);
            v
        }

        let mut memo: HashMap<i32, i32> = HashMap::new();
        helper(n, &mut memo)
    }
}

fn main() {
    println!("{}", Solution::climb_stairs(5)); // 8
}

Solution 3 - Tabulation (Bottom-Up DP)

Build up the solution iteratively from the base cases. We fill a DP array where dp[i] represents the number of ways to reach step i. Each step is the sum of the two preceding steps.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0070.3 - Climbing Stairs - Solution 3 - Tabulation (Bottom-Up DP) """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def climbStairs(self, n: int) -> int:
        """Climbing Stairs Function"""
        if n <= 2:
            return n

        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2

        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]

        return dp[n]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().climbStairs(2))   # 2
    print(Solution().climbStairs(3))   # 3
    print(Solution().climbStairs(5))   # 8


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

/** 0070.3 - Climbing Stairs - Solution 3 - Tabulation (Bottom-Up DP) */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class Solution {
    /** Climbing Stairs Function */
    climbStairs(n) {
        if (n <= 2) return n;

        const dp = new 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];
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase() {
    /** Test Function */
    const solution = new Solution();
    console.log(solution.climbStairs(2)); // 2
    console.log(solution.climbStairs(3)); // 3
    console.log(solution.climbStairs(5)); // 8
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

/** 0070.3 - Climbing Stairs - Solution 3 - Tabulation (Bottom-Up DP) */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class Solution {
    /** Climbing Stairs Function */
    climbStairs(n: number): number {
        if (n <= 2) return n;

        const dp: number[] = new 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];
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase(): void {
    /** Test Function */
    const solution = new Solution();
    console.log(solution.climbStairs(2)); // 2
    console.log(solution.climbStairs(3)); // 3
    console.log(solution.climbStairs(5)); // 8
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

// 0070.3 - Climbing Stairs - Solution 3 - Tabulation (Bottom-Up DP)

package main

/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
import "fmt"

/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
func climbStairsDP(n int) int {
	if n <= 2 {
		return n
	}

	dp := make([]int, n+1)
	dp[1] = 1
	dp[2] = 2

	for i := 3; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	return dp[n]
}

func testcase() {
	// Test Function
	fmt.Println(climbStairsDP(2)) // 2
	fmt.Println(climbStairsDP(3)) // 3
	fmt.Println(climbStairsDP(5)) // 8
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
func main() {
	testcase()
}

// 0070.3 - Climbing Stairs - Solution 3 - Tabulation (Bottom-Up DP)

struct Solution;

impl Solution {
    /// Climbing Stairs Function
    pub fn climb_stairs(n: i32) -> i32 {
        if n <= 2 {
            return n;
        }

        let n = n as usize;
        let mut dp: Vec<i32> = vec![0; n + 1];
        dp[1] = 1;
        dp[2] = 2;

        for i in 3..=n {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        dp[n]
    }
}

fn main() {
    println!("{}", Solution::climb_stairs(5)); // 8
}

Solution 4 - Space-Optimized DP

Since we only need the last two values at each step, we can reduce space to O(1) by using two variables instead of a full array. This is the most efficient approach.

TimeComplexity: O(n)

SpaceComplexity: O(1)

""" 0070.4 - Climbing Stairs - Solution 4 - Space-Optimized DP """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def climbStairs(self, n: int) -> int:
        """Climbing Stairs Function"""
        if n <= 2:
            return n

        prev2 = 1
        prev1 = 2
        for _ in range(3, n + 1):
            prev2, prev1 = prev1, prev1 + prev2
        return prev1


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().climbStairs(2))   # 2
    print(Solution().climbStairs(3))   # 3
    print(Solution().climbStairs(5))   # 8


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

/** 0070.4 - Climbing Stairs - Solution 4 - Space-Optimized DP */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class Solution {
    /** Climbing Stairs Function */
    climbStairs(n) {
        if (n <= 2) return n;

        let prev2 = 1;
        let prev1 = 2;
        for (let i = 3; i <= n; i++) {
            const cur = prev1 + prev2;
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase() {
    /** Test Function */
    const solution = new Solution();
    console.log(solution.climbStairs(2)); // 2
    console.log(solution.climbStairs(3)); // 3
    console.log(solution.climbStairs(5)); // 8
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

/** 0070.4 - Climbing Stairs - Solution 4 - Space-Optimized DP */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class Solution {
    /** Climbing Stairs Function */
    climbStairs(n: number): number {
        if (n <= 2) return n;

        let prev2: number = 1;
        let prev1: number = 2;
        for (let i = 3; i <= n; i++) {
            const cur: number = prev1 + prev2;
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase(): void {
    /** Test Function */
    const solution = new Solution();
    console.log(solution.climbStairs(2)); // 2
    console.log(solution.climbStairs(3)); // 3
    console.log(solution.climbStairs(5)); // 8
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

// 0070.4 - Climbing Stairs - Solution 4 - Space-Optimized DP

package main

/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
import "fmt"

/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
func climbStairsOptimized(n int) int {
	if n <= 2 {
		return n
	}

	prev2 := 1
	prev1 := 2
	for i := 3; i <= n; i++ {
		cur := prev1 + prev2
		prev2 = prev1
		prev1 = cur
	}
	return prev1
}

func testcase() {
	// Test Function
	fmt.Println(climbStairsOptimized(2)) // 2
	fmt.Println(climbStairsOptimized(3)) // 3
	fmt.Println(climbStairsOptimized(5)) // 8
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
func main() {
	testcase()
}

// 0070.4 - Climbing Stairs - Solution 4 - Space-Optimized DP

struct Solution;

impl Solution {
    /// Climbing Stairs Function
    pub fn climb_stairs(n: i32) -> i32 {
        if n <= 2 {
            return n;
        }

        let mut prev2: i32 = 1;
        let mut prev1: i32 = 2;
        for _ in 3..=n {
            let cur = prev1 + prev2;
            prev2 = prev1;
            prev1 = cur;
        }
        prev1
    }
}

fn main() {
    println!("{}", Solution::climb_stairs(5)); // 8
}

0070 - Climbing Stairs

Solution 1 - Recursive (Brute Force)

Solution 2 - Memoization (Top-Down DP)

Solution 3 - Tabulation (Bottom-Up DP)

Solution 4 - Space-Optimized DP