Climbing Stairs Problem in DSA Java

Mental Model

You want to find how many ways you can reach the top by taking 1 or 2 steps at a time.

Analogy: Imagine climbing a staircase where you can step up either one stair or skip one to land two stairs ahead. Counting all possible ways to reach the top is like counting all paths you can take by choosing 1 or 2 steps each time.

Start: 0
Steps: 1 2 3 4 5 ... n
You can move: 0 -> 1 or 0 -> 2 -> 3 or 2 -> 4 -> 5
Each arrow means a possible step of size 1 or 2.

Dry Run Walkthrough

Input: stairs = 4

Goal: Find how many distinct ways to reach step 4 from step 0 by taking 1 or 2 steps at a time.

Step 1: Calculate ways to reach step 1

ways[0]=1 (base), ways[1]=1 (only one way: 0->1)

Why: Base cases: only one way to stand still and one way to take first step

Step 2: Calculate ways to reach step 2

ways[2] = ways[1] + ways[0] = 1 + 1 = 2

Why: You can get to step 2 from step 1 or step 0

Step 3: Calculate ways to reach step 3

ways[3] = ways[2] + ways[1] = 2 + 1 = 3

Why: You can get to step 3 from step 2 or step 1

Step 4: Calculate ways to reach step 4

ways[4] = ways[3] + ways[2] = 3 + 2 = 5

Why: You can get to step 4 from step 3 or step 2

Result:

ways array: [1, 1, 2, 3, 5]
Answer: 5 ways to climb 4 stairs

Annotated Code

DSA Java

public class ClimbingStairs {
    public static int climbStairs(int n) {
        if (n <= 1) return 1; // base case: 1 way to stand still or 1 step
        int[] ways = new int[n + 1];
        ways[0] = 1; // 1 way to stay at step 0
        ways[1] = 1; // 1 way to reach step 1
        for (int i = 2; i <= n; i++) {
            ways[i] = ways[i - 1] + ways[i - 2]; // sum ways from previous two steps
        }
        return ways[n];
    }

    public static void main(String[] args) {
        int stairs = 4;
        int result = climbStairs(stairs);
        System.out.println("Number of ways to climb " + stairs + " stairs: " + result);
    }
}

if (n <= 1) return 1; // base case: 1 way to stand still or 1 step

handle smallest inputs directly

ways[0] = 1; // 1 way to stay at step 0

initialize base case for step 0

ways[1] = 1; // 1 way to reach step 1

initialize base case for step 1

for (int i = 2; i <= n; i++) { ways[i] = ways[i - 1] + ways[i - 2]; }

calculate ways to reach each step by summing ways to previous two steps

return ways[n];

return total ways to reach step n

Output

Number of ways to climb 4 stairs: 5

Complexity Analysis

Time: O(n) because we compute ways for each step once from 2 to n

Space: O(n) because we store ways for all steps from 0 to n

vs Alternative: Compared to recursive approach without memoization which is exponential, this dynamic programming approach is efficient and avoids repeated calculations

Edge Cases

n = 0 (no stairs)

Returns 1 because standing still counts as one way

DSA Java

if (n <= 1) return 1;

n = 1 (one stair)

Returns 1 because only one step to climb

DSA Java

if (n <= 1) return 1;

large n (e.g., 45)

Calculates efficiently without stack overflow or repeated work

DSA Java

for (int i = 2; i <= n; i++) { ways[i] = ways[i - 1] + ways[i - 2]; }

When to Use This Pattern

When you see a problem asking for number of ways to reach a point with fixed step sizes, use dynamic programming to build solutions from smaller subproblems.

Common Mistakes

Mistake: Using recursion without memoization causing exponential time and stack overflow
Fix: Use bottom-up dynamic programming with an array to store intermediate results

Mistake: Not handling base cases correctly leading to wrong answers for small inputs
Fix: Explicitly return 1 when n is 0 or 1 to cover base cases

Summary

Calculates how many distinct ways to climb n stairs taking 1 or 2 steps at a time.

Use when counting paths or combinations with fixed step increments.

The number of ways to reach step n equals sum of ways to reach steps n-1 and n-2.

Practice

1. What does the Climbing Stairs problem ask you to find?
Given n steps, how many distinct ways can you climb to the top if you can take 1 or 2 steps at a time?

easy

A. The maximum number of steps you can take at once

B. The minimum number of steps to reach the top

C. The total number of distinct ways to reach the top

D. The number of steps you skip

Solution

1. Step 1: Understand the problem statement

   The problem asks for the count of different ways to climb to the top using 1 or 2 steps at a time.

2. Step 2: Identify what is being counted

   We count all possible sequences of 1-step and 2-step moves that sum to n steps.

3. Final Answer:

   The total number of distinct ways to reach the top -> Option C

4. Quick Check:

   Counting ways = total distinct sequences [OK]

Hint: Count sequences of 1 or 2 steps summing to n [OK]

Common Mistakes:

• Confusing number of ways with minimum steps
• Thinking about maximum steps allowed
• Counting skipped steps instead of ways

2. Which of the following Java method signatures correctly represents a function to solve the Climbing Stairs problem for n steps?

easy

A. public int climbStairs(int n)

B. public void climbStairs(int n)

C. public int climbStairs()

D. public int climbStairs(String n)

Solution

1. Step 1: Check method return type and parameters

   The method should return an integer count and accept an integer input for steps.

2. Step 2: Validate each option

   public int climbStairs(int n) returns int and takes int n, which fits the problem. Others either have wrong return type or parameter type.

3. Final Answer:

   public int climbStairs(int n) -> Option A

4. Quick Check:

   Return int count, input int steps [OK]

Hint: Return int, input int n for steps [OK]

Common Mistakes:

• Using void return type instead of int
• Missing input parameter
• Using wrong parameter type like String

3. What is the output of the following Java code snippet?

public class Solution {
  public static int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2, c = 0;
    for (int i = 3; i <= n; i++) {
      c = a + b;
      a = b;
      b = c;
    }
    return c;
  }
  public static void main(String[] args) {
    System.out.println(climbStairs(4));
  }
}

medium

A. 3

B. 7

C. 4

D. 5

Solution

1. Step 1: Trace the loop for n=4

   Initial a=1, b=2. Loop runs for i=3 and i=4.
   i=3: c=1+2=3, a=2, b=3
   i=4: c=2+3=5, a=3, b=5

2. Step 2: Return value after loop

   Return c=5, which is the number of ways to climb 4 steps.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   Ways(4) = 5 [OK]

Hint: Use Fibonacci-like addition for steps > 2 [OK]

Common Mistakes:

• Returning b instead of c
• Off-by-one errors in loop
• Misunderstanding base cases

4. Identify the error in the following Java code for climbing stairs:

public int climbStairs(int n) {
  if (n == 1) return 1;
  int[] dp = new int[n];
  dp[0] = 1;
  dp[1] = 2;
  for (int i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
  }
  return dp[n];
}

medium

A. Wrong return statement should be dp[n-1]

B. Array index out of bounds due to dp size and loop range

C. Incorrect base case for n == 1

D. Missing initialization of dp[2]

Solution

1. Step 1: Check array size and indexing

   Array dp size is n, but loop runs i from 2 to n inclusive, accessing dp[n], which is out of bounds.

2. Step 2: Identify correct loop range and return

   Loop should run i < n, and return dp[n-1] to avoid index error.

3. Final Answer:

   Array index out of bounds due to dp size and loop range -> Option B

4. Quick Check:

   Loop index exceeds array size [OK]

Hint: Array size n means max index n-1 [OK]

Common Mistakes:

• Looping to i <= n instead of i < n
• Returning dp[n] instead of dp[n-1]
• Incorrect base case handling

5. You want to find the number of ways to climb 10 steps but now you can take 1, 2, or 3 steps at a time. Which approach correctly adapts the Climbing Stairs problem?

hard

A. Use dp[i] = dp[i-1] + dp[i-2] + dp[i-3] with base dp[0]=1, dp[1]=1, dp[2]=2

B. Use dp[i] = dp[i-1] * dp[i-2] * dp[i-3] with base dp[0]=1

C. Use dp[i] = dp[i-1] + dp[i-2] only, ignoring 3 steps

D. Use recursion without memoization for all steps

Solution

1. Step 1: Understand the new step options

   Since you can take 1, 2, or 3 steps, ways to reach step i depend on previous 3 steps.

2. Step 2: Formulate dp relation and base cases

   dp[i] = dp[i-1] + dp[i-2] + dp[i-3]. Base cases: dp[0]=1 (one way to stand still), dp[1]=1, dp[2]=2.

3. Final Answer:

   Use dp[i] = dp[i-1] + dp[i-2] + dp[i-3] with base dp[0]=1, dp[1]=1, dp[2]=2 -> Option A

4. Quick Check:

   Include all step sizes in dp sum [OK]

Hint: Sum dp of last 3 steps for 1,2,3 step moves [OK]

Common Mistakes:

• Ignoring 3-step moves in dp formula
• Multiplying dp values instead of adding
• Using recursion without caching causing slow run