# Climbing Stairs

EASY

You are climbing a staircase. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Given n will be a positive integer. Consider the following example:

Example:

```Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps```

In a simple brute force approach, we can take all possible step combinations i.e. 1 and 2, at every step. At every step, we are calling the method `climb` for step 1 and 2, and return the sum of returned values of both methods.

`climbStairs(i,n) = climbStairs((i+1), n) + climbStairs((i+2),n);`

where `i` defines the current stair and `n` defines the destination stair. Following is the recursive implementation:

```int destination = 0;
public int climbStairs(int n) {
destination = n;
return climb(0);
}

private int climb(int currentStairNo) {
if (currentStairNo > destination) return 0;
if (currentStairNo == destination) return 1;
return climb(currentStairNo + 1) + climb(currentStairNo + 2);
}
```

Time Complexity : `O(2n)`. The size of the recursion tree will be `2n`. The recursion tree for destination stair 3.

In the previous approach, we are redundantly calculating the result for every step. Instead, we can store the result at each step in `memo` array and directly returning the result from the memo array whenever that function is called again. As we can see in the above figure we are calculation `climb(2) = climb(3) + climb(4)` two times. Following is the recursion with memoization:

```int destination = 0;
int[] memo = null;
public int climbStairs(int n) {
memo = new int[n + 1];
destination = n;
return climb(0);
}

private int climb(int currentStairNo) {
if (currentStairNo > destination) return 0;
if (currentStairNo == destination) return 1;
if (memo[currentStairNo] > 0) return memo[currentStairNo];
memo[currentStairNo] = climb(currentStairNo + 1) + climb(currentStairNo + 2);
return memo[currentStairNo];
}
```

• Time Complexity: `O(n)`. Size of recursion tree can go up to `n`.
• Space Complexity: `O(n)`. The depth of the recursion tree can go up to `n`.

Dynamic Programming:

As we can see this problem can be broken into subproblems, and it contains the optimal substructure property i.e. its optimal solution can be constructed efficiently from optimal solutions of its subproblems, we can use dynamic programming to solve this problem. One can reach the ith step in one of the two ways:

1. Taking a single step from `(i−1)th` step.
2. Taking a step of 2 from  `(i−2)th `step.

So, the total number of ways to reach ith is equal to the sum of ways of reaching `(i−1)th` step and ways of reaching `(i−2)th` step. Let `dp[i]` denotes the number of ways to reach on ith step:

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

Complexity Analysis :

• Time Complexity : `O(n)`. Single loop up to `n`.
• Space Complexity : `O(n)``dp` array of size `n` is used.

Categories: Dynamic Programming