Introduction
Climbing Stairs is a classic problem in computer science that involves finding the number of distinct ways one can climb a staircase of n steps. In this problem, we assume that one can take either 1 or 2 steps at a time.
Problem Statement
Given an integer n, find the number of distinct ways one can climb a staircase of n steps.
Data Structure used
We will be using two data structures in this problem: a vector and a double.
Algorithmic approach
There are two approaches to solve the Climbing Stairs problem: the dynamic programming approach and the Fibonacci sequence approach.
Dynamic Programming approach
We will create a vector dp of size n+1 to store the number of distinct ways to reach each step. Initially, we set dp[0] = 1 and dp[1] = 1. We then iterate through the remaining steps, calculating dp[i] = dp[i-1] + dp[i-2] for each step. Finally, we return dp[n], which contains the number of distinct ways to climb the staircase.
int climbStairsDynamicProgramming(int n)
{
if (n == 0 || n == 1)
{
return 1;
}
vector<int> dp(n + 1);
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
Fibonacci Sequence approach
We can use the formula for the nth term of the Fibonacci sequence to solve the Climbing Stairs problem. The formula is:
F(n) = (phi^n - (1-phi)^n) / sqrt(5)
where phi is the golden ratio (1 + sqrt(5)) / 2.
int climbStairsFibonacci(int n)
{
double phi = (1 + sqrt(5)) / 2;
return round(pow(phi, n + 1) / sqrt(5));
}
Time Complexity
The time complexity of the dynamic programming approach is O(n), as we need to iterate through each step once to calculate the number of distinct ways to reach that step. The time complexity of the Fibonacci sequence approach is O(1), as we can calculate the nth term of the Fibonacci sequence in constant time.
Space Complexity
The space complexity of both approaches is O(n), as we need to store n+1 elements in the dp vector for the dynamic programming approach, and we need to store phi in the Fibonacci sequence approach.
Conclusion
In this blog post, we discussed two approaches to solving the Climbing Stairs problem: the dynamic programming approach and the Fibonacci sequence approach. While the dynamic programming approach has a time complexity of O(n) and a space complexity of O(n), the Fibonacci sequence approach has a time complexity of O(1) and a space complexity of O(1). Therefore, the Fibonacci sequence approach is more efficient for larger values of n.