Climbing Stairs - Dynamic Programming Java Interview Guide
Learn the Climbing Stairs Dynamic Programming problem in Java using recursion, memoization, tabulation, and constant-space optimization with complete code, dry runs, internal working, complexity analysis, common mistakes, and interview questions.
Introduction
The Climbing Stairs problem is one of the most important beginner-level Dynamic Programming problems.
It teaches how to:
- Identify a recurrence relation
- Convert recursion into Dynamic Programming
- Use Memoization
- Use Tabulation
- Optimize memory from
O(n)toO(1) - Recognize that different paths can lead to the same state
Although the problem looks like a simple counting problem, it introduces the same reasoning used in more advanced Dynamic Programming problems such as:
- House Robber
- Coin Change
- Decode Ways
- Minimum Cost Climbing Stairs
- Unique Paths
- Jump Game
Problem Statement
You are climbing a staircase containing n steps.
You can climb either:
1 step
or
2 steps
at a time.
Return the total number of distinct ways to reach the top.
Example 1
Input:
n = 2
Output:
2
Explanation:
Way 1
1 + 1
Way 2
2
Example 2
Input:
n = 3
Output:
3
Explanation:
1 + 1 + 1
1 + 2
2 + 1
Example 3
Input:
n = 5
Output:
8
The eight possible ways are:
1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 2
1 + 1 + 2 + 1
1 + 2 + 1 + 1
2 + 1 + 1 + 1
1 + 2 + 2
2 + 1 + 2
2 + 2 + 1
Core Intuition
To reach step n, the final move must come from one of two places.
You either:
Come from step n - 1
and climb 1 step
or:
Come from step n - 2
and climb 2 steps
Therefore:
ways(n)
=
ways(n - 1)
+
ways(n - 2)
This is the same recurrence relation as the Fibonacci sequence.
Recurrence Relation
ways(n) = ways(n - 1) + ways(n - 2)
Base cases:
ways(1) = 1
ways(2) = 2
Another valid definition is:
ways(0) = 1
ways(1) = 1
The value ways(0) = 1 represents one valid way to remain at the starting point without taking any steps.
Why Is This a Dynamic Programming Problem?
The problem contains the two main characteristics of Dynamic Programming.
1. Overlapping Subproblems
The same values are calculated repeatedly.
For example:
ways(5)
├── ways(4)
│ ├── ways(3)
│ └── ways(2)
└── ways(3)
ways(3) is calculated more than once.
2. Optimal Substructure
The answer for a larger staircase can be constructed from answers to smaller staircases.
ways(5)
=
ways(4)
+
ways(3)
Decision Tree
For n = 4:
graph TD
ways_0_0["ways"] --> ways_1_1["ways"]
ways_0_0["ways"] --> N_3_1_2["3"]
N_4_0_1["4"] --> ways_1_3["ways"]
N_4_0_1["4"] --> N_2_1_4["2"]
ways_1_1["ways"] --> ways_2_1["ways"]
ways_1_1["ways"] --> N_2_2_2["2"]
N_3_1_2["3"] --> ways_2_3["ways"]
N_3_1_2["3"] --> N_1_2_4["1"]
ways_1_3["ways"] --> ways_2_5["ways"]
ways_1_3["ways"] --> N_1_2_6["1"]
N_2_1_4["2"] --> ways_2_7["ways"]
N_2_1_4["2"] --> N_0_2_8["0"]
ways_2_1["ways"] --> ways_3_1["ways"]
ways_2_1["ways"] --> N_1_3_2["1"]
N_2_2_2["2"] --> ways_3_3["ways"]
N_2_2_2["2"] --> N_0_3_4["0"]
The tree shows repeated subproblems such as:
ways(2)
ways(1)
ways(0)
Memoization stores these answers and prevents repeated computation.
Approach 1: Brute-Force Recursion
Idea
At every step, make one of two choices:
Take 1 step
or
Take 2 steps
Recursively count the number of ways produced by both choices.
Complete Java Code
public class ClimbingStairsRecursion {
public static int climbStairs(int n) {
if (n == 0) {
return 1;
}
if (n < 0) {
return 0;
}
int oneStepWays = climbStairs(n - 1);
int twoStepWays = climbStairs(n - 2);
return oneStepWays + twoStepWays;
}
public static void main(String[] args) {
int n = 5;
int result = climbStairs(n);
System.out.println(
"Number of ways to climb "
+ n
+ " stairs: "
+ result
);
}
}
Output:
Number of ways to climb 5 stairs: 8
Step-by-Step Explanation of Recursive Code
Step 1: Method Input
public static int climbStairs(int n)
n represents the number of steps still remaining.
Step 2: Successful Completion
if (n == 0) {
return 1;
}
When n becomes 0, we have reached the top successfully.
Therefore, this path contributes one valid way.
Step 3: Invalid Path
if (n < 0) {
return 0;
}
When n becomes negative, we climbed beyond the staircase.
This path is invalid and contributes zero ways.
Step 4: Take One Step
int oneStepWays = climbStairs(n - 1);
This calculates the number of ways after taking one step.
Step 5: Take Two Steps
int twoStepWays = climbStairs(n - 2);
This calculates the number of ways after taking two steps.
Step 6: Combine Both Possibilities
return oneStepWays + twoStepWays;
The total answer is the sum of:
Ways after taking 1 step
+
Ways after taking 2 steps
Recursive Dry Run for n = 3
climbStairs(3)
=
climbStairs(2)
+
climbStairs(1)
Expand climbStairs(2):
climbStairs(2)
=
climbStairs(1)
+
climbStairs(0)
Expand climbStairs(1):
climbStairs(1)
=
climbStairs(0)
+
climbStairs(-1)
Base values:
climbStairs(0) = 1
climbStairs(-1) = 0
Therefore:
climbStairs(1) = 1
climbStairs(2) = 2
climbStairs(3) = 3
Complexity of Brute-Force Recursion
| Metric | Complexity |
|---|---|
| Time | O(2ⁿ) |
| Space | O(n) |
The time complexity is exponential because every call can generate two more recursive calls.
The recursion depth can reach n, resulting in O(n) call-stack space.
This approach is useful for understanding the recurrence relation, but it is not recommended as the final interview solution.
Approach 2: Memoization
Idea
Store the result for every previously calculated staircase size.
Before calculating ways(n), check whether it is already available in the cache.
This converts the exponential solution into a linear-time solution.
Memoization Flow
graph TD
Call_ways_n["Call ways(n)"] --> Is_answer_already_cached["Is answer already cached?"]
Is_answer_already_cached["Is answer already cached?"] --> N_["│"]
N_["│"] --> No["└── No"]
No["└── No"] --> Calculate_ways_n_1_ways_n_2["Calculate ways(n - 1) + ways(n - 2)"]
Calculate_ways_n_1_ways_n_2["Calculate ways(n - 1) + ways(n - 2)"] --> Store_answer["Store answer"]
Store_answer["Store answer"] --> Return_answer["Return answer"]
Complete Java Code Using Memoization
import java.util.Arrays;
public class ClimbingStairsMemoization {
public static int climbStairs(int n) {
if (n < 0) {
throw new IllegalArgumentException(
"Number of stairs cannot be negative"
);
}
int[] memo = new int[n + 1];
Arrays.fill(memo, -1);
return climb(n, memo);
}
private static int climb(int n, int[] memo) {
if (n == 0 || n == 1) {
return 1;
}
if (memo[n] != -1) {
return memo[n];
}
int oneStepWays = climb(n - 1, memo);
int twoStepWays = climb(n - 2, memo);
memo[n] = oneStepWays + twoStepWays;
return memo[n];
}
public static void main(String[] args) {
int[] testCases = {0, 1, 2, 3, 5, 10};
for (int n : testCases) {
int result = climbStairs(n);
System.out.println(
"n = "
+ n
+ ", ways = "
+ result
);
}
}
}
Output:
n = 0, ways = 1
n = 1, ways = 1
n = 2, ways = 2
n = 3, ways = 3
n = 5, ways = 8
n = 10, ways = 89
Step-by-Step Explanation of Memoization Code
Step 1: Validate Input
if (n < 0) {
throw new IllegalArgumentException(
"Number of stairs cannot be negative"
);
}
A negative staircase size is invalid.
Step 2: Create Memoization Array
int[] memo = new int[n + 1];
Each index stores the answer for that number of stairs.
For example:
memo[3]
=
number of ways to climb 3 stairs
Step 3: Initialize Uncomputed States
Arrays.fill(memo, -1);
-1 means that a result has not yet been calculated.
Step 4: Define Base Cases
if (n == 0 || n == 1) {
return 1;
}
There is:
1 way to climb 0 stairs
1 way to climb 1 stair
Step 5: Check the Cache
if (memo[n] != -1) {
return memo[n];
}
When the answer was already calculated, return it immediately.
Step 6: Calculate Smaller Problems
int oneStepWays = climb(n - 1, memo);
int twoStepWays = climb(n - 2, memo);
These represent the two possible final moves.
Step 7: Store the Result
memo[n] = oneStepWays + twoStepWays;
The answer is stored before being returned.
Memoization Dry Run for n = 5
Initial cache:
Index
0 1 2 3 4 5
Memo
-1 -1 -1 -1 -1 -1
Calculate:
graph TD
climb_5["climb(5)"] --> climb_4["climb(4)"]
climb_4["climb(4)"] --> climb_3["climb(3)"]
climb_3["climb(3)"] --> climb_2["climb(2)"]
For climb(2):
climb(1) + climb(0)
=
1 + 1
=
2
Cache:
memo[2] = 2
For climb(3):
memo[2] + climb(1)
=
2 + 1
=
3
Cache:
memo[3] = 3
For climb(4):
memo[3] + memo[2]
=
3 + 2
=
5
Cache:
memo[4] = 5
For climb(5):
memo[4] + memo[3]
=
5 + 3
=
8
Final cache:
Index
0 1 2 3 4 5
Memo
-1 -1 2 3 5 8
Answer:
8
Complexity of Memoization
| Metric | Complexity |
|---|---|
| Time | O(n) |
| Memo Array | O(n) |
| Recursion Stack | O(n) |
| Total Space | O(n) |
Each state from 0 to n is calculated at most once.
Approach 3: Tabulation
Idea
Build the result from the smallest staircase size to the requested staircase size.
Instead of using recursion, use an iterative loop.
DP State
dp[i]
=
number of distinct ways to reach step i
Base Cases
dp[0] = 1
dp[1] = 1
State Transition
dp[i]
=
dp[i - 1]
+
dp[i - 2]
Complete Java Code Using Tabulation
import java.util.Arrays;
public class ClimbingStairsTabulation {
public static int climbStairs(int n) {
if (n < 0) {
throw new IllegalArgumentException(
"Number of stairs cannot be negative"
);
}
if (n == 0 || n == 1) {
return 1;
}
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
System.out.println(
"DP table: " + Arrays.toString(dp)
);
return dp[n];
}
public static void main(String[] args) {
int n = 5;
int result = climbStairs(n);
System.out.println(
"Number of ways: " + result
);
}
}
Output:
DP table: [1, 1, 2, 3, 5, 8]
Number of ways: 8
Step-by-Step Explanation of Tabulation
For:
n = 5
Initialize:
dp[0] = 1
dp[1] = 1
Calculate dp[2]:
dp[2]
=
dp[1] + dp[0]
=
1 + 1
=
2
Calculate dp[3]:
dp[3]
=
dp[2] + dp[1]
=
2 + 1
=
3
Calculate dp[4]:
dp[4]
=
dp[3] + dp[2]
=
3 + 2
=
5
Calculate dp[5]:
dp[5]
=
dp[4] + dp[3]
=
5 + 3
=
8
Final table:
Index
0 1 2 3 4 5
Ways
1 1 2 3 5 8
Complexity of Tabulation
| Metric | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) |
Tabulation avoids recursion overhead and stack overflow risk.
Approach 4: Space-Optimized Dynamic Programming
Observation
To calculate the current answer, we only need:
ways for the previous step
and
ways for two steps before
The entire DP array is unnecessary.
Variable Meaning
previousTwo
=
ways to reach i - 2
previousOne
=
ways to reach i - 1
current
=
ways to reach i
Complete Java Code Using O(1) Space
public class ClimbingStairsOptimized {
public static long climbStairs(int n) {
if (n < 0) {
throw new IllegalArgumentException(
"Number of stairs cannot be negative"
);
}
if (n == 0 || n == 1) {
return 1;
}
long previousTwo = 1;
long previousOne = 1;
for (int currentStep = 2;
currentStep <= n;
currentStep++) {
long currentWays =
previousOne + previousTwo;
previousTwo = previousOne;
previousOne = currentWays;
}
return previousOne;
}
public static void main(String[] args) {
int[] testCases = {
0,
1,
2,
3,
5,
10,
20,
45
};
for (int n : testCases) {
long result = climbStairs(n);
System.out.printf(
"Number of ways to climb %d stairs: %d%n",
n,
result
);
}
}
}
Output:
Number of ways to climb 0 stairs: 1
Number of ways to climb 1 stairs: 1
Number of ways to climb 2 stairs: 2
Number of ways to climb 3 stairs: 3
Number of ways to climb 5 stairs: 8
Number of ways to climb 10 stairs: 89
Number of ways to climb 20 stairs: 10946
Number of ways to climb 45 stairs: 1836311903
Step-by-Step Dry Run of Optimized Solution
For:
n = 5
Initial values:
previousTwo = 1
previousOne = 1
These represent:
ways(0) = 1
ways(1) = 1
Current Step = 2
currentWays
=
previousOne + previousTwo
=
1 + 1
=
2
Update:
previousTwo = 1
previousOne = 2
Current Step = 3
currentWays
=
2 + 1
=
3
Update:
previousTwo = 2
previousOne = 3
Current Step = 4
currentWays
=
3 + 2
=
5
Update:
previousTwo = 3
previousOne = 5
Current Step = 5
currentWays
=
5 + 3
=
8
Update:
previousTwo = 5
previousOne = 8
Final result:
8
Optimized State Visualization
Step 0
previousTwo = 1
Step 1
previousOne = 1
Move forward:
current = previousOne + previousTwo
Then shift:
previousTwo = previousOne
previousOne = current
Visualization:
graph TD
Before["Before"] --> previousTwo_previousOne["previousTwo previousOne"]
previousTwo_previousOne["previousTwo previousOne"] --> N_3_5["3 5"]
N_3_5["3 5"] --> Current_3_5_8["Current = 3 + 5 = 8"]
After shifting:
previousTwo previousOne
5 8
Complexity Comparison
| Approach | Time | Space | Recommendation |
|---|---|---|---|
| Brute-Force Recursion | O(2ⁿ) | O(n) | Explain only |
| Memoization | O(n) | O(n) | Good top-down solution |
| Tabulation | O(n) | O(n) | Good bottom-up solution |
| Space Optimized | O(n) | O(1) | Best interview solution |
Complete Interview-Ready Java Solution
This version includes:
- Input validation
- Constant-space optimization
longreturn type- Multiple test cases
- Clear method naming
public final class ClimbingStairs {
private ClimbingStairs() {
// Utility class
}
public static long countWays(int numberOfStairs) {
if (numberOfStairs < 0) {
throw new IllegalArgumentException(
"Number of stairs must be zero or greater"
);
}
if (numberOfStairs == 0
|| numberOfStairs == 1) {
return 1;
}
long waysToPreviousTwoSteps = 1;
long waysToPreviousStep = 1;
for (int step = 2;
step <= numberOfStairs;
step++) {
long waysToCurrentStep =
waysToPreviousStep
+ waysToPreviousTwoSteps;
waysToPreviousTwoSteps =
waysToPreviousStep;
waysToPreviousStep =
waysToCurrentStep;
}
return waysToPreviousStep;
}
public static void main(String[] args) {
verify(0, 1);
verify(1, 1);
verify(2, 2);
verify(3, 3);
verify(4, 5);
verify(5, 8);
verify(10, 89);
System.out.println(
"All test cases passed."
);
}
private static void verify(
int stairs,
long expected
) {
long actual = countWays(stairs);
if (actual != expected) {
throw new AssertionError(
"Failed for stairs="
+ stairs
+ ". Expected="
+ expected
+ ", actual="
+ actual
);
}
System.out.printf(
"stairs=%d, ways=%d%n",
stairs,
actual
);
}
}
Output:
stairs=0, ways=1
stairs=1, ways=1
stairs=2, ways=2
stairs=3, ways=3
stairs=4, ways=5
stairs=5, ways=8
stairs=10, ways=89
All test cases passed.
Why Use long Instead of int?
The number of possible ways increases rapidly.
For example:
n = 45
ways = 1,836,311,903
This still fits inside a Java int.
However:
n = 46
ways = 2,971,215,073
This exceeds the maximum int value:
2,147,483,647
Therefore, using long supports larger values.
For extremely large values, use BigInteger.
BigInteger Solution for Large n
import java.math.BigInteger;
public class ClimbingStairsBigInteger {
public static BigInteger climbStairs(int n) {
if (n < 0) {
throw new IllegalArgumentException(
"Number of stairs cannot be negative"
);
}
if (n == 0 || n == 1) {
return BigInteger.ONE;
}
BigInteger previousTwo =
BigInteger.ONE;
BigInteger previousOne =
BigInteger.ONE;
for (int step = 2; step <= n; step++) {
BigInteger current =
previousOne.add(previousTwo);
previousTwo = previousOne;
previousOne = current;
}
return previousOne;
}
public static void main(String[] args) {
int n = 100;
System.out.println(
"Ways to climb "
+ n
+ " stairs: "
+ climbStairs(n)
);
}
}
For n = 100, the result is:
573147844013817084101
Variations of Climbing Stairs
The standard problem allows:
1 step
or
2 steps
Interviewers often introduce additional constraints.
Variation 1: Allow 1, 2, or 3 Steps
Recurrence:
ways(n)
=
ways(n - 1)
+
ways(n - 2)
+
ways(n - 3)
Java code:
public static long climbStairsWithThreeMoves(int n) {
if (n < 0) {
return 0;
}
if (n == 0) {
return 1;
}
long[] dp = new long[n + 1];
dp[0] = 1;
for (int step = 1; step <= n; step++) {
dp[step] += dp[step - 1];
if (step >= 2) {
dp[step] += dp[step - 2];
}
if (step >= 3) {
dp[step] += dp[step - 3];
}
}
return dp[n];
}
Variation 2: Custom Allowed Steps
Suppose allowed jumps are:
[1, 3, 5]
Recurrence:
dp[i]
=
dp[i - 1]
+
dp[i - 3]
+
dp[i - 5]
Complete Java code:
public class CustomClimbingStairs {
public static long countWays(
int numberOfStairs,
int[] allowedSteps
) {
if (numberOfStairs < 0) {
throw new IllegalArgumentException(
"Number of stairs cannot be negative"
);
}
if (allowedSteps == null
|| allowedSteps.length == 0) {
return numberOfStairs == 0 ? 1 : 0;
}
long[] dp =
new long[numberOfStairs + 1];
dp[0] = 1;
for (int currentStep = 1;
currentStep <= numberOfStairs;
currentStep++) {
for (int allowedStep : allowedSteps) {
if (allowedStep <= 0) {
throw new IllegalArgumentException(
"Allowed step sizes must be positive"
);
}
if (currentStep >= allowedStep) {
dp[currentStep] +=
dp[currentStep - allowedStep];
}
}
}
return dp[numberOfStairs];
}
public static void main(String[] args) {
int numberOfStairs = 6;
int[] allowedSteps = {1, 3, 5};
System.out.println(
countWays(
numberOfStairs,
allowedSteps
)
);
}
}
Variation 3: Minimum Cost Climbing Stairs
In this variation, each step has an associated cost.
The objective is not to count paths.
The objective is to find the minimum cost required to reach the top.
Transition:
dp[i]
=
cost[i]
+
min(
dp[i - 1],
dp[i - 2]
)
This demonstrates how a counting problem can become an optimization problem while keeping a similar DP structure.
Climbing Stairs vs Fibonacci
| Feature | Climbing Stairs | Fibonacci |
|---|---|---|
| Recurrence | ways(n−1) + ways(n−2) | fib(n−1) + fib(n−2) |
| Base Case 0 | 1 | 0 |
| Base Case 1 | 1 | 1 |
| Main Goal | Count paths | Generate sequence value |
| DP Pattern | Linear DP | Linear DP |
The recurrence is similar, but the base cases differ.
Climbing Stairs vs Backtracking
A Backtracking solution explicitly explores every possible sequence:
1,1,1,1
1,1,2
1,2,1
2,1,1
2,2
Dynamic Programming does not need to generate each path.
It only stores the number of ways to reach each step.
| Approach | Behavior |
|---|---|
| Backtracking | Generates every path |
| Dynamic Programming | Counts paths using smaller states |
Use Backtracking when the interviewer asks to return all paths.
Use Dynamic Programming when the interviewer asks only for the count.
Production Use Cases
The staircase is an abstraction for moving through sequential states.
Workflow Navigation
A workflow may allow moving one or two stages ahead.
Dynamic Programming can count possible execution paths.
Approval Systems
An approval request may advance through regular or expedited stages.
The same recurrence can model possible approval sequences.
Network Routing
A service may advance through one or two adjacent network hops.
DP can count valid routing paths.
Game Development
A player may move one or two positions per turn.
The algorithm can calculate possible movement sequences.
Manufacturing Pipelines
A process can move to the next station or skip one station.
DP can model possible production flows.
Subscription Upgrade Paths
Users may upgrade one tier at a time or skip to the next eligible tier.
The number of possible upgrade sequences can be counted.
Retry Workflows
A process may retry the current stage or skip to a fallback stage.
The same state-transition thinking can be applied.
Common Mistakes
1. Returning 0 for n = 0
In this problem:
ways(0) = 1
There is one valid way to climb zero stairs: take no action.
2. Using Fibonacci Base Cases Directly
Fibonacci uses:
fib(0) = 0
fib(1) = 1
Climbing Stairs commonly uses:
ways(0) = 1
ways(1) = 1
The recurrence is the same, but the base cases are different.
3. Writing Only the Recursive Solution
The recursive solution is exponential.
Always discuss Memoization, Tabulation, or space optimization.
4. Allocating an Array Before Handling Small Inputs
This can fail:
int[] dp = new int[n + 1];
dp[1] = 1;
When n = 0, index 1 does not exist.
Handle small inputs first.
5. Updating Variables in the Wrong Order
Incorrect:
previousOne = current;
previousTwo = previousOne;
After the first line, the old previousOne value is lost.
Correct:
previousTwo = previousOne;
previousOne = current;
6. Ignoring Integer Overflow
Use:
long
for moderately large inputs and:
BigInteger
for very large inputs.
7. Confusing Count With Minimum Steps
The problem asks for the number of distinct ways.
It does not ask for the minimum number of moves.
8. Generating All Paths Unnecessarily
Generating every path uses exponential time and memory.
Use DP when only the number of paths is required.
Interview Problem-Solving Approach
Follow these steps during an interview.
Step 1: Identify the State
dp[i]
=
number of ways to reach step i
Step 2: Identify the Last Decision
The final move is either:
1 step from i - 1
or
2 steps from i - 2
Step 3: Write the Transition
dp[i]
=
dp[i - 1]
+
dp[i - 2]
Step 4: Define Base Cases
dp[0] = 1
dp[1] = 1
Step 5: Choose an Implementation
Start with:
Memoization or Tabulation
Then optimize to:
O(1) space
Step 6: Verify Edge Cases
Test:
n = 0
n = 1
n = 2
n = 3
Interview Explanation
A clear interview explanation could be:
To reach stair
n, the previous position must be either stairn−1or stairn−2. Therefore, the number of ways to reach stairnis the sum of the ways to reach those two previous stairs. This creates the recurrencedp[n] = dp[n−1] + dp[n−2]. Since every state depends only on the previous two states, I can reduce the memory usage fromO(n)toO(1).
Frequently Asked Interview Questions
1. Why is Climbing Stairs a Dynamic Programming problem?
Answer
Because the same smaller subproblems are calculated repeatedly, and the answer for a larger staircase is built from answers to smaller staircases.
2. What is the recurrence relation?
Answer
ways(n)
=
ways(n - 1)
+
ways(n - 2)
3. Why do we use ways(0) = 1?
Answer
It represents one valid way to complete a staircase with zero remaining steps: take no additional move.
4. What is the time complexity of recursion?
Answer
The brute-force recursive solution takes approximately O(2ⁿ) time because each call can create two more recursive calls.
5. What is the time complexity of the DP solution?
Answer
Memoization and Tabulation both take O(n) time.
6. Can the space complexity be reduced?
Answer
Yes. Since each state depends only on the previous two states, the space complexity can be reduced to O(1).
7. How is Climbing Stairs related to Fibonacci?
Answer
They use the same recurrence relation, but the initial values are different.
8. What changes when three steps are allowed?
Answer
The recurrence becomes:
ways(n)
=
ways(n - 1)
+
ways(n - 2)
+
ways(n - 3)
9. What should be used for very large n?
Answer
Use Java's BigInteger because both int and long eventually overflow.
10. What is the biggest mistake candidates make?
Answer
They often implement only exponential recursion or use incorrect base cases copied directly from Fibonacci.
Quick Revision
| Topic | Summary |
|---|---|
| Problem | Count ways to climb n stairs |
| Allowed Moves | 1 or 2 steps |
| DP State | dp[i] = ways to reach step i |
| Transition | dp[i] = dp[i−1] + dp[i−2] |
| Base Cases | dp[0] = 1, dp[1] = 1 |
| Brute-Force Time | O(2ⁿ) |
| DP Time | O(n) |
| Optimized Space | O(1) |
| Best Java Type | long or BigInteger |
| Interview Frequency | ⭐⭐⭐⭐⭐ |
Key Takeaways
- Climbing Stairs is a foundational one-dimensional Dynamic Programming problem.
- The final step must come from either
n−1orn−2. - This produces the recurrence
ways(n) = ways(n−1) + ways(n−2). - Brute-force recursion takes exponential time because it recalculates overlapping subproblems.
- Memoization and Tabulation reduce the time complexity to
O(n). - Since only two previous states are needed, memory can be reduced to
O(1). - The same reasoning extends to custom step sizes, minimum-cost paths, workflow transitions, and other sequential state problems.