# Climbing Stairs Leetcode problem solution

## Climbing Stairs - A Dynamic Programming Approach

## Table of contents

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 step + 1 step

2 steps

```
Input: n = 3
Output: 3
```

The 3 ways are:

1 step + 1 step + 1 step

1 step + 2 steps

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.