# Leetcode : 0070 : Climbing Stairs (DP)
###### tags:`leetcode`
You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

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

Input: n = 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

first solution : Recursion

DP[n] = DP[n-1]+DP[n-2]

C++:

> Base Fibonacci solution DP[n] = DP[n-1] + DP[n-2]

class Solution {
    public:
        int climbStairs(int n) {
            vector<int> memo(n + 1);
            return helper(n, memo);
        }

        int helper(int n, vector<int>& memo) {
            if (n <= 1) return 1;
            if (memo[n] > 1) return memo[n];
            return memo[n] = helper(n - 1, memo) + helper(n - 2, memo);
            }
    
};
    

> Trapezoidal Area

class Solution {
    public:
    int climbStairs(int n) {
        if(n <= 1) return 1;
        return climbStairs(n / 2) * climbStairs(n - n / 2) + climbStairs(n / 2 - 1) * climbStairs(n - n / 2 - 1);
    }
    //Trapezoidal Area
};

> fibonacci formulation

class Solution {
    public:
    int climbStairs(int n) {
        double root5 = sqrt(5);
        return (1 / root5) * (pow((1 + root5) / 2, n + 1) - pow((1 - root5) / 2, n + 1));
    }
    //fibonacci formulation 
};

class Solution03 {
public:
    int climbStairs(int n) {
        if (n==0) return 0;
        if (n==1) return 1;
        int first = 1;
        int second = 2;
        for (int i=3; i<=n ; i++){
            int thrid = first + second; 
            //dp = dp[n-1] + dp[n-2] ,dp[3] = dp[1]+dp[2] 
            // next run dp[4] = dp[2] + dp[3]
            
            first = second; //move next dp[1] = dp[2]
            second = thrid; //move next dp[2] = dp[3]
        }
        return second;
    }
};

// n            [1] [2] [3] [4] [5] [6] [7]
// sum method   0+1 1+1 2+1 2+3 3+5 5+8 8+13
// value         1   2   3   5   8   13  21
// (n-1)+(n-2)