Description: You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Brute-force Approach

Recursively calculate the number of ways to reach the top by taking 1 or 2 steps at each level. Use the recursive formula f(n) = f(n - 1) + f(n - 2).

Time: O(2^n)

Space: O(1), O(n) Recursive stack space

Memoization Approach

Use an array as a cache to store the results of sub problems, that is, the number of ways to reach each level, and use it to avoid recomputation.

Time: O(n)

Space: O(n), O(n) Recursive stack space

Tabulation Approach

To save recursive stack space, use a bottom-up approach. Instead of recursion, use a loop to calculate the number of ways to reach each level, storing the results of sub problems in an array.

Time: O(n)

Space: O(n)

Optimal Approach

Since we need only f(n - 1) and f(n - 2), use two variables instead of an entire array to store the number of ways to reach the current level and the previous level. Loop through the levels, updating the variables at each step.

Time: O(n)

Space: O(1)