Question: Leetcode question

The Climbing Stairs problem is a very common coding interview question frequently seen on sites like LeetCode. Given a staircase with n steps, you can climb either 1 or 2 steps at a time. The question is: in how many distinct ways can you climb to the top?

This is a classic dynamic programming problem that starts with a simple recursive solution but has redundant sub-problems. We can optimize it using techniques like memoization or tabulation with a table.

Examples

Input: n = 2 
Output: 2

The 2 ways are:

1. 1 step + 1 step

2. 2 steps

Input: n = 3
Output: 3

The 3 ways are:

1. 1 step + 1 step + 1 step

2. 1 step + 2 steps

3. 2 steps + 1 step

Visually, the recursive tree looks like:

    n=3
   / \
  n=2 n=1 
 / \
n=1 n=0

We can see redundant sub-problems are being solved repeatedly.

Recursive Solution

A simple recursive brute force solution is:

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

This has exponential O(2^n) time complexity and O(n) space complexity due to the recursion stack.

Dynamic Programming Solution

We can optimize this using dynamic programming with a table to store intermediate results.

Tabulation approach:

int climbStairs(int n) {
  if (n <= 2) return n;

  int[] table = new int[n]; // Initialize table of size n

  // Base cases
  table[1] = 1;  
  table[2] = 2;

  // Build table bottom-up 
  for (int i = 3; i <= n; i++) {    
    table[i] = table[i-1] + table[i-2];
  }

  return table[n];
}

• We initialize the base cases of 1 step and 2 steps.

• Then we iteratively build the table bottom-up, using the results from previous steps.

• For any step i, the number of ways to climb i steps is equal to:

  • The number of ways to climb i-1 steps (1 step from i-1 to i)

  • Plus the number of ways to climb i-2 steps (2 steps from i-2 to i)

• This gives us the final result in table[n].

The tabulation approach improves time complexity to O(n) and maintains O(n) space complexity by storing the table.

Conclusion

This example demonstrates how dynamic programming can optimize slow recursive solutions by storing intermediate results in a table. The tabulation approach transforms an exponential time solution to a linear time and space solution. DP is an important technique for improving algorithm efficiency.