Climbing Stairs*******

https://leetcode.com/problems/climbing-stairs/solution/

solution is Really AweSome

You are climbing a stair case. 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?

Example
Given an example n=3 , 1+1+1=2+1=1+2=3
return 3

time O (2 ^ n)

space O(n)

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

public class Solution {
    public int climbStairs(int n) {
        if (n == 0 ){
            return 0;
        }
        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];
    }
}

In this brute force approach we take all possible step combinations
 i.e. 1 and 2, at every step. At every step we are calling the function climbStairs for step 1 and 2, 
 and return the sum of returned values of both functions.
climbStairs(i,n)=climbStairs(i+1,n)+climbStairs(i+2,n), 
where i defines the current step and n defines the destination step.

Approach #2 Recursion with memorization

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.

In this way we are pruning recursion tree with the help of memo array and reducing the size of recursion tree up to n.

Complexity Analysis

• Time complexity :O(n)O(n). Size of recursion tree can go uptonn.

• Space complexity :O(n)O(n). The depth of recursion tree can go up to n.