Problem
You are climbing a staircase withn steps. Each time, you can climb either 1 step or 2 steps. Return the number of distinct ways you can reach the top.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
n = 4Output
5Explanation
1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2
Solution
To reach stepn, the last move must come from either step n - 1 by taking 1 step, or from step n - 2 by taking 2 steps.
Therefore, the number of ways to reach a step is:
ways(n) = ways(n - 1) + ways(n - 2)class Solution {
public int climbStairs(int n) {
Integer[] memo = new Integer[n + 1];
return climbStairsHelper(n, memo);
}
private int climbStairsHelper(int n, Integer[] memo) {
// 0 -> No steps needed
// 1 -> Only one way
// 2 -> Two ways: 1 and 2
if (n <= 2) {
return n;
}
if (memo[n] != null) {
return memo[n];
}
// Ways taking 2 steps + ways taking 1 step
return memo[n] =
climbStairsHelper(n - 2, memo)
+ climbStairsHelper(n - 1, memo);
}
}
Complexity
Each state from0 to n is calculated only once, resulting in O(n) time complexity. The memoization array and recursion stack require O(n) space.
Tabulation Approach
Instead of solving the problem recursively, we can build the solution from the bottom up using a DP array.The array stores the number of ways to reach each step. We start with the base cases and calculate each subsequent value using the previous two values.
public int climbStairs(int n) {
if (n <= 1) {
return 1;
}
int[] dp = new int[n + 1];
// Base cases.
dp[0] = 1;
dp[1] = 1;
// Build each step from the previous two.
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
Complexity
Each step is calculated once, resulting inO(n) time complexity. The DP array stores n + 1 values, requiring O(n) space.
Space Optimized Approach
In the tabulation approach, each value depends only on the previous two values. Therefore, storing the entire DP array is unnecessary.We can keep only the number of ways to reach the previous two steps and update them as we move forward.
public int climbStairs(int n) {
if (n <= 1) {
return 1;
}
int previous = 1;
int current = 1;
for (int i = 2; i <= n; i++) {
int next = previous + current;
previous = current;
current = next;
}
return current;
}
Complexity
Each step is processed once, resulting inO(n) time complexity. Only a constant number of variables are used, reducing the space complexity to O(1).