# Climbing Stairs

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?

**Note:**Given _n _will be a positive integer.

**Example 1:**

Input:

2

Output:

2

Explanation:

There are two ways to climb to the top.

1. 1 step + 1 step

2. 2 steps

**Example 2:**

Input:

3

Output:

3

Explanation:

There are three ways to climb to the top.

1. 1 step + 1 step + 1 step

2. 1 step + 2 steps

3. 2 steps + 1 step

**DP - Bottom Up Approach**

Break this problem into subproblems, with optimal substructure, thus using Dynamic Programming (Bottom Up approach):

State:`dp[i]`

- number of ways to reach the`ith`

stepState Transfer Function:`dp[i] = dp[i - 1] + dp[i - 2]`

- taking a step from (i - 1), or taking a step of 2 from (i - 2)Initial State:`dp[0] = 0;`

`dp[1] = 1;`

`dp[2] = 2;`

Answer:`dp[n]`

Complexity Analysis

Time complexity: O(n). Single loop up to`n`

. Space complexity : O(n).`dp`

array of size`n`

is used.

**DP - Top-Down Approach - Recursion with memorization**

We could define

`memo[]`

to store the number of ways to `ith`

step, it helps pruning recursion. And the recursive function could be defined as `climb_Stairs(int i, int n, int memo[])`

that returns the number of ways from `ith`

step to `nth`

step.Complexity Analysis

Time complexity : O(n). Single loop upto n. Space complexity : O(n). dpdp array of size n is used.

**DP - Fibonacci Number - Optimize Space Complexity**

`Fib(n)=Fib(n−1)+Fib(n−2)`

That the nth number only has to do with its previous two numbers, thus we don't have to maintain a whole array of results, just the last 2 results are enough. Thus optimized the space for O(1).

**Complexity Analysis**

- Time complexity :
`O(n)`

. Single loop upto n is required to calculate`n th`

fibonacci number. - Space complexity :
`O(1)`

. Constant space is used.

Dynamic Programming - Bottom Up - O(n) space, O(n) time (3ms 32.02% AC)

class Solution {

public int climbStairs(int n) {

if (n == 0) return 0;

if (n == 1) return 1;

if (n == 2) return 2;

int[] steps = new int[n + 1];

steps[0] = 0;

steps[1] = 1;

steps[2] = 2;

for (int i = 3; i < n + 1; i++) {

steps[i] = steps[i - 1] + steps[i - 2];

}

return steps[n];

}

}

Dynamic Programming - Recursion with memorization - Top Down - O(n) Space, O(n) Time (3ms 32.02%)

public class Solution {

public int climbStairs(int n) {

int memo[] = new int[n + 1];

return climb_Stairs(0, n, memo);

}

public int climb_Stairs(int i, int n, int memo[]) {

if (i > n) {

return 0;

}

if (i == n) {

return 1;

}

if (memo[i] > 0) {

return memo[i];

}

memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);

return memo[i];

}

}

DP - Fibonacci Numbers - Space Optimized (2ms 92.09%)

public class Solution {

public int climbStairs(int n) {

if (n == 1) {

return 1;

}

int first = 1;

int second = 2;

for (int i = 3; i <= n; i++) {

int third = first + second;

first = second;

second = third;

}

return second;

}

}

Last modified 2yr ago