Climbing Stairs

🎯

Climbing Stairs

easyDPAmazonGoogleApple

Imagine you are climbing a staircase with n steps, and you can take either 1 or 2 steps at a time. How many distinct ways can you reach the top?

💡 This problem is a classic example of counting the number of ways to reach a target using small steps. Beginners often struggle because the problem looks simple but requires recognizing overlapping subproblems and optimal substructure, which are key to dynamic programming.

📋

Problem Statement

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? Input: integer n (number of steps). Output: integer representing the number of distinct ways to reach the top.

1 ≤ n ≤ 10^5

💡

Example

Input"n = 3"

Output3

There are three ways: 1+1+1, 1+2, 2+1

• n = 1 → 1 (only one way: single step)
• n = 2 → 2 (two ways: 1+1 or 2)
• n = 0 → 1 (one way: stand still, base case)
• n = 10^5 → large input to test efficiency

🔁

Why DP?

Why greedy fails:

A greedy approach might try to always take 2 steps when possible, but this misses some combinations. For example, for n=3, greedy would count only 2+1, missing 1+1+1 and 1+2.

DP state:

dp[i] represents the number of distinct ways to reach step i.

Recurrence:dp[i] = dp[i-1] + dp[i-2]

The number of ways to reach step i is the sum of ways to reach the previous step and the step before that.

⚠️

Common Mistakes

Not handling base cases correctly

Incorrect results or runtime errors

✅ Explicitly define dp[0] and dp[1] as 1

Using recursion without memoization

Exponential time leading to TLE

✅ Add memoization or switch to bottom-up DP

Off-by-one errors in loops or dp array indexing

Wrong answers or index errors

✅ Carefully define dp array size and loop ranges

Not optimizing space when asked

Uses unnecessary memory, may fail large tests

✅ Use two variables instead of full dp array

Assuming greedy approach works

Misses valid combinations, incorrect count

✅ Use DP to consider all combinations

🧠

Brute Force (Pure Recursion)

💡 This approach helps understand the problem's recursive nature and overlapping subproblems, even though it is inefficient.

Intuition

At each step, you can climb either 1 or 2 steps. So, the total ways to reach step n is the sum of ways to reach n-1 and n-2.

Algorithm

1. Define a recursive function ways(n) that returns the number of ways to reach step n.
2. If n is 0 or 1, return 1 as base cases.
3. Otherwise, return ways(n-1) + ways(n-2).
4. Call ways(n) to get the final answer.

💡 The recursion tree grows exponentially because each call branches into two calls, making it hard to track without memoization.

Recurrence:dp[i] = dp[i-1] + dp[i-2]

</>

Code

def climb_stairs(n):
    if n <= 1:
        return 1
    return climb_stairs(n-1) + climb_stairs(n-2)

# Driver code
if __name__ == '__main__':
    n = 3
    print(climb_stairs(n))  # Output: 3

Line Notes

def climb_stairs(n):Defines the recursive function to compute ways to climb n steps

if n <= 1:Base case: 1 way to climb 0 or 1 step

return 1Return 1 for base cases to stop recursion

return climb_stairs(n-1) + climb_stairs(n-2)Recursive call summing ways from previous two steps

public class ClimbingStairs {
    public static int climbStairs(int n) {
        if (n <= 1) return 1;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }

    public static void main(String[] args) {
        int n = 3;
        System.out.println(climbStairs(n)); // Output: 3
    }
}

Line Notes

public static int climbStairs(int n)Recursive method to compute ways to climb n steps

if (n <= 1) return 1;Base case: 1 way to climb 0 or 1 step

return climbStairs(n - 1) + climbStairs(n - 2);Sum ways from previous two steps recursively

System.out.println(climbStairs(n));Prints the result for given n

#include <iostream>
using namespace std;

int climbStairs(int n) {
    if (n <= 1) return 1;
    return climbStairs(n - 1) + climbStairs(n - 2);
}

int main() {
    int n = 3;
    cout << climbStairs(n) << endl; // Output: 3
    return 0;
}

Line Notes

int climbStairs(int n)Recursive function to calculate ways to climb n steps

if (n <= 1) return 1;Base case for 0 or 1 step

return climbStairs(n - 1) + climbStairs(n - 2);Recursive calls summing previous two results

cout << climbStairs(n) << endl;Output the final result

function climbStairs(n) {
    if (n <= 1) return 1;
    return climbStairs(n - 1) + climbStairs(n - 2);
}

console.log(climbStairs(3)); // Output: 3

Line Notes

function climbStairs(n)Defines recursive function for climbing stairs

if (n <= 1) return 1;Base case for 0 or 1 step

return climbStairs(n - 1) + climbStairs(n - 2);Sum ways from previous two steps recursively

console.log(climbStairs(3));Prints the result for input 3

⏱

Complexity

TimeO(2^n)

SpaceO(n) due to recursion stack

Each call branches into two calls, leading to exponential growth in calls.

💡 For n=20, this means over a million calls, which is very inefficient.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem's recursive structure.

🧠

Top-Down DP (Memoization)

💡 Memoization avoids recomputing the same subproblems by caching results, drastically improving efficiency.

Intuition

Store results of ways to climb steps already computed, so recursive calls reuse these values instead of recomputing.

Algorithm

1. Create a cache (dictionary or array) to store results for each step.
2. Define a recursive function that checks the cache before computing.
3. If result is cached, return it; else compute recursively and store in cache.
4. Return the cached result for the original input n.

💡 Memoization transforms exponential recursion into linear time by avoiding duplicate work.

Recurrence:dp[i] = dp[i-1] + dp[i-2]

</>

Code

def climb_stairs(n, memo=None):
    if memo is None:
        memo = {}
    if n <= 1:
        return 1
    if n in memo:
        return memo[n]
    memo[n] = climb_stairs(n-1, memo) + climb_stairs(n-2, memo)
    return memo[n]

# Driver code
if __name__ == '__main__':
    n = 3
    print(climb_stairs(n))  # Output: 3

Line Notes

def climb_stairs(n, memo=None):Defines recursive function with memo dictionary

if memo is None:Initialize memo dictionary on first call

if n <= 1:Base case: 1 way to climb 0 or 1 step

if n in memo:Return cached result if available to avoid recomputation

memo[n] = climb_stairs(n-1, memo) + climb_stairs(n-2, memo)Compute and cache result for n

import java.util.HashMap;

public class ClimbingStairs {
    private static HashMap<Integer, Integer> memo = new HashMap<>();

    public static int climbStairs(int n) {
        if (n <= 1) return 1;
        if (memo.containsKey(n)) return memo.get(n);
        int result = climbStairs(n - 1) + climbStairs(n - 2);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        int n = 3;
        System.out.println(climbStairs(n)); // Output: 3
    }
}

Line Notes

private static HashMap<Integer, Integer> memoCache to store computed results

if (n <= 1) return 1;Base case for recursion

if (memo.containsKey(n)) return memo.get(n);Return cached result if present

memo.put(n, result);Store computed result in cache

#include <iostream>
#include <unordered_map>
using namespace std;

unordered_map<int,int> memo;

int climbStairs(int n) {
    if (n <= 1) return 1;
    if (memo.find(n) != memo.end()) return memo[n];
    memo[n] = climbStairs(n - 1) + climbStairs(n - 2);
    return memo[n];
}

int main() {
    int n = 3;
    cout << climbStairs(n) << endl; // Output: 3
    return 0;
}

Line Notes

unordered_map<int,int> memo;Cache to store computed results

if (n <= 1) return 1;Base case for recursion

if (memo.find(n) != memo.end()) return memo[n];Return cached result if found

memo[n] = climbStairs(n - 1) + climbStairs(n - 2);Compute and cache result

const memo = {};
function climbStairs(n) {
    if (n <= 1) return 1;
    if (memo[n]) return memo[n];
    memo[n] = climbStairs(n - 1) + climbStairs(n - 2);
    return memo[n];
}

console.log(climbStairs(3)); // Output: 3

Line Notes

const memo = {};Cache object to store computed results

if (n <= 1) return 1;Base case for recursion

if (memo[n]) return memo[n];Return cached result if available

memo[n] = climbStairs(n - 1) + climbStairs(n - 2);Compute and cache result

⏱

Complexity

TimeO(n)

SpaceO(n) due to recursion stack and memo storage

Each subproblem is solved once and stored, reducing calls from exponential to linear.

💡 For n=20, this means about 20 calls instead of over a million.

Interview Verdict: Accepted

This approach is efficient enough for large inputs and demonstrates dynamic programming principles.

🧠

Bottom-Up DP (Tabulation)

💡 This approach builds the solution iteratively from the base cases up to n, avoiding recursion overhead.

Intuition

Start from the smallest steps and iteratively compute ways to reach each step until n.

Algorithm

1. Initialize a dp array of size n+1.
2. Set dp[0] = 1 and dp[1] = 1 as base cases.
3. Iterate i from 2 to n, setting dp[i] = dp[i-1] + dp[i-2].
4. Return dp[n] as the final answer.

💡 This approach is easier to debug and understand since it uses iteration and explicit storage.

Recurrence:dp[i] = dp[i-1] + dp[i-2]

</>

Code

def climb_stairs(n):
    if n <= 1:
        return 1
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

# Driver code
if __name__ == '__main__':
    n = 3
    print(climb_stairs(n))  # Output: 3

Line Notes

if n <= 1:Handle base cases directly

dp = [0] * (n + 1)Initialize dp array to store ways for each step

dp[0], dp[1] = 1, 1Base cases: 1 way to stand still or take one step

for i in range(2, n + 1):Iterate through steps to fill dp table

dp[i] = dp[i - 1] + dp[i - 2]Sum ways from previous two steps

public class ClimbingStairs {
    public static int climbStairs(int n) {
        if (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];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        int n = 3;
        System.out.println(climbStairs(n)); // Output: 3
    }
}

Line Notes

if (n <= 1) return 1;Handle base cases

int[] dp = new int[n + 1];Create dp array to store results

dp[0] = 1; dp[1] = 1;Initialize base cases

for (int i = 2; i <= n; i++)Iterate to fill dp array

dp[i] = dp[i - 1] + dp[i - 2];Compute ways for step i

#include <iostream>
#include <vector>
using namespace std;

int climbStairs(int n) {
    if (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];
}

int main() {
    int n = 3;
    cout << climbStairs(n) << endl; // Output: 3
    return 0;
}

Line Notes

if (n <= 1) return 1;Handle base cases

vector<int> dp(n + 1);Create dp vector to store ways

dp[0] = 1; dp[1] = 1;Initialize base cases

for (int i = 2; i <= n; i++)Iterate to fill dp vector

dp[i] = dp[i - 1] + dp[i - 2];Calculate ways for step i

function climbStairs(n) {
    if (n <= 1) return 1;
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

console.log(climbStairs(3)); // Output: 3

Line Notes

if (n <= 1) return 1;Handle base cases

const dp = new Array(n + 1).fill(0);Initialize dp array

dp[0] = 1; dp[1] = 1;Set base cases

for (let i = 2; i <= n; i++)Iterate to fill dp array

dp[i] = dp[i - 1] + dp[i - 2];Compute ways for step i

⏱

Complexity

TimeO(n)

SpaceO(n) for dp array

Iterates once through n steps, storing results in dp array.

💡 For n=100000, this approach is efficient and feasible.

Interview Verdict: Accepted

This is a standard DP solution that is efficient and easy to implement.

🧠

Space Optimized DP

💡 Since dp[i] depends only on the previous two values, we can optimize space by storing only two variables instead of the whole array.

Intuition

Keep track of only the last two computed values to save memory.

Algorithm

1. Initialize two variables first and second to 1, representing ways to reach steps 0 and 1.
2. Iterate from step 2 to n, computing current ways as sum of first and second.
3. Update first and second to move forward in the sequence.
4. Return second as the number of ways to reach step n.

💡 This approach reduces space from O(n) to O(1) while maintaining linear time complexity.

Recurrence:dp[i] = dp[i-1] + dp[i-2]

</>

Code

def climb_stairs(n):
    if n <= 1:
        return 1
    first, second = 1, 1
    for _ in range(2, n + 1):
        current = first + second
        first, second = second, current
    return second

# Driver code
if __name__ == '__main__':
    n = 3
    print(climb_stairs(n))  # Output: 3

Line Notes

if n <= 1:Handle base cases directly

first, second = 1, 1Initialize variables for steps 0 and 1

for _ in range(2, n + 1):Iterate through steps from 2 to n

current = first + secondCalculate ways for current step

first, second = second, currentUpdate variables for next iteration

public class ClimbingStairs {
    public static int climbStairs(int n) {
        if (n <= 1) return 1;
        int first = 1, second = 1;
        for (int i = 2; i <= n; i++) {
            int current = first + second;
            first = second;
            second = current;
        }
        return second;
    }

    public static void main(String[] args) {
        int n = 3;
        System.out.println(climbStairs(n)); // Output: 3
    }
}

Line Notes

if (n <= 1) return 1;Handle base cases

int first = 1, second = 1;Initialize variables for first two steps

for (int i = 2; i <= n; i++)Iterate through steps

int current = first + second;Calculate current ways

first = second; second = current;Update variables for next iteration

#include <iostream>
using namespace std;

int climbStairs(int n) {
    if (n <= 1) return 1;
    int first = 1, second = 1;
    for (int i = 2; i <= n; i++) {
        int current = first + second;
        first = second;
        second = current;
    }
    return second;
}

int main() {
    int n = 3;
    cout << climbStairs(n) << endl; // Output: 3
    return 0;
}

Line Notes

if (n <= 1) return 1;Handle base cases

int first = 1, second = 1;Initialize variables for first two steps

for (int i = 2; i <= n; i++)Iterate through steps

int current = first + second;Calculate current ways

first = second; second = current;Update variables for next iteration

function climbStairs(n) {
    if (n <= 1) return 1;
    let first = 1, second = 1;
    for (let i = 2; i <= n; i++) {
        let current = first + second;
        first = second;
        second = current;
    }
    return second;
}

console.log(climbStairs(3)); // Output: 3

Line Notes

if (n <= 1) return 1;Handle base cases

let first = 1, second = 1;Initialize variables for first two steps

for (let i = 2; i <= n; i++)Iterate through steps

let current = first + second;Calculate current ways

first = second; second = current;Update variables for next iteration

⏱

Complexity

TimeO(n)

SpaceO(1)

Iterates once through n steps, storing only two variables.

💡 This approach is optimal for both time and space.

Interview Verdict: Accepted

This is the best practical solution for large inputs due to minimal memory usage.

📊

All Approaches - One-Glance Tradeoffs

💡 Space optimized DP is best for interviews; memoization and tabulation are good intermediate steps; brute force is only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	N/A	Mention only - never code
2. Top-Down DP (Memoization)	O(n)	O(n) recursion stack + memo	Possible for very large n	Yes	Good to code if comfortable with recursion
3. Bottom-Up DP (Tabulation)	O(n)	O(n)	No	Yes	Safe and clear iterative solution
4. Space Optimized DP	O(n)	O(1)	No	No (without extra storage)	Best practical solution to code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Present the brute force recursive solution to show understanding.Step 3: Optimize with memoization to improve efficiency.Step 4: Show bottom-up tabulation for iterative clarity.Step 5: Present space-optimized solution for best performance.Step 6: Test with edge cases and discuss complexity.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

Interviewer tests your understanding of recursion, dynamic programming concepts, optimization techniques, and ability to write clean code.

Common Follow-ups

• What if you can climb 1, 2, or 3 steps at a time? → Modify recurrence to dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
• How to reconstruct the actual sequences? → Use backtracking with dp array

💡 These follow-ups test your ability to generalize and extend the solution.

🔍

Pattern Recognition

When to Use

1) Problem asks for number of ways or counts; 2) Steps or states depend on fixed previous states; 3) Overlapping subproblems exist; 4) Optimal substructure is present.

Signature Phrases

number of distinct waysclimb 1 or 2 stepsreach the top

NOT This Pattern When

Problems requiring greedy or combinatorial math without overlapping subproblems

Similar Problems

Fibonacci Number - same recurrence relationHouse Robber - linear DP with similar state transitions

Practice

1. Consider the following Python code implementing the optimal solution for the House Robber II problem. What is the final output when the input is [2, 3, 2]?

def rob_linear(nums, start, end):
    prev, curr = 0, 0
    for i in range(start, end + 1):
        prev, curr = curr, max(curr, prev + nums[i])
    return curr

def rob(nums):
    n = len(nums)
    if n == 1:
        return nums[0]
    return max(rob_linear(nums, 0, n - 2), rob_linear(nums, 1, n - 1))

print(rob([2,3,2]))

easy

A. 4

B. 2

C. 3

D. 5

Solution

1. Step 1: Trace rob_linear(nums, 0, 1)

   nums[0]=2, nums[1]=3 Iteration i=0: prev=0, curr=0 -> prev=0, curr=max(0,0+2)=2 Iteration i=1: prev=2, curr=max(2,0+3)=3 Return 3

2. Step 2: Trace rob_linear(nums, 1, 2)

   nums[1]=3, nums[2]=2 Iteration i=1: prev=0, curr=0 -> prev=0, curr=max(0,0+3)=3 Iteration i=2: prev=3, curr=max(3,0+2)=3 Return 3 Max(3,3) = 3

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Both cases yield 3, final output is 3 [OK]

Hint: Trace both linear cases and pick max [OK]

Common Mistakes:

• Off-by-one in loop range
• Confusing which subarray to use
• Incorrect max calculation

2. You are given a list of non-negative integers representing the amount of money in each house along a street. You want to maximize the total amount you can rob tonight without robbing two adjacent houses. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. Dynamic programming that considers robbing or skipping each house to maximize total

B. A greedy algorithm that always picks the house with the maximum amount next

C. Sorting the houses by amount and picking the top half

D. Depth-first search exploring all subsets of houses

Solution

1. Step 1: Understand problem constraints

   The problem requires maximizing sum without robbing adjacent houses, which is a classic overlapping subproblems scenario.

2. Step 2: Identify suitable algorithm

   Dynamic programming fits because it explores choices at each house (rob or skip) and uses previous results to build optimal solution.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy fails on cases like [2,7,9,3,1], DP finds max 12 [OK]

Hint: DP handles overlapping subproblems and optimal substructure [OK]

Common Mistakes:

• Greedy approach fails on non-adjacent constraints

3. Suppose the cooldown constraint is removed, allowing buying immediately after selling. Which modification to the DP state machine yields the correct optimal profit?

hard

A. Remove the 'cool' state and update 'hold' as max(hold, free - prices[i]) with free = max(free, free)

B. Use a greedy approach buying at every local minimum and selling at every local maximum

C. Keep 'cool' state but allow buying on cooldown day by updating hold = max(hold, cool - prices[i])

D. Remove 'cool' state and update hold = max(hold, free - prices[i]) with free = max(free, free)

Solution

1. Step 1: Understand cooldown removal effect

   Without cooldown, no need to track cooldown state; buying can happen immediately after selling.

2. Step 2: Adjust DP states

   Remove 'cool' state; hold updated as max(hold, free - prices[i]); free updated as max(free, free) (effectively unchanged).

3. Step 3: Why other options fail

   Keeping 'cool' or using greedy breaks correctness or adds unnecessary complexity.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Removing cooldown state matches classic Best Time II problem [OK]

Hint: No cooldown means no cooldown state needed [OK]

Common Mistakes:

• Trying to keep cooldown state unnecessarily
• Using greedy which fails on some inputs

4. Suppose the problem is modified so that you can buy and sell the same stock multiple times on the same day (i.e., unlimited transactions per day allowed). Which modification to the original DP solution correctly handles this variant?

hard

A. Remove the transaction fee from the sell operation since multiple transactions per day are allowed.

B. Modify the DP to allow multiple buys and sells per day by iterating over all possible transactions per day, increasing time complexity to O(n²).

C. Keep the original state machine but remove the fee subtraction on sell, and update hold and cash as usual.

D. Allow buying even if already holding stock by removing the hold state check, updating hold = max(hold, cash - price) unconditionally.

Solution

1. Step 1: Understand the variant

   Multiple transactions per day means multiple buys and sells can happen on the same day, which breaks the original assumption of one transaction per day.

2. Step 2: Analyze solution impact

   The original DP assumes at most one buy or sell per day; to handle multiple transactions per day, the DP must consider all possible transaction counts per day, increasing complexity to O(n²).

3. Step 3: Evaluate options

   Simply removing fees or allowing buys while holding leads to invalid states or incorrect profits. Only enumerating all transactions per day correctly models the problem.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Handling multiple transactions per day requires more complex DP with nested loops [OK]

Hint: Multiple transactions per day require enumerating all transaction counts [OK]

Common Mistakes:

• Removing fees incorrectly
• Allowing invalid states by buying while holding

5. Suppose the House Robber problem is modified so you can rob the same house multiple times (unlimited reuse). Which of the following changes to the algorithm correctly computes the maximum amount you can rob?

hard

A. Use the original DP but allow robbing adjacent houses since reuse is allowed

B. Use unbounded knapsack approach: dp[i] = max(dp[i], dp[i - 1] + nums[i]) iterating until no improvement

C. Use a new DP where dp[i] = max(dp[i-1], dp[i-2] + nums[i]) but allow revisiting dp[i] multiple times

D. Modify DP to consider robbing the current house plus the best solution including the current house again (i.e., dp[i] = max(dp[i-1], dp[i] + nums[i]))

Solution

1. Step 1: Understand problem change

   Allowing unlimited reuse means we can rob the same house multiple times, similar to unbounded knapsack.

2. Step 2: Identify correct DP formulation

   Unbounded knapsack style DP updates dp[i] considering dp[i - 1] + nums[i] repeatedly until stable.

3. Step 3: Evaluate options

   Use unbounded knapsack approach: dp[i] = max(dp[i], dp[i - 1] + nums[i]) iterating until no improvement correctly describes iterative updates until no improvement, matching unbounded knapsack logic.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Original adjacency constraints no longer apply; unbounded knapsack DP fits [OK]

Hint: Reuse means unbounded knapsack, not original adjacency DP [OK]

Common Mistakes:

• Trying to reuse original adjacency DP
• Ignoring repeated state updates