# 4 Ways to Solve <a href="https://leetcode.com/problems/climbing-stairs/"> 70. Climbing Stairs </a>

### 1. Recursion
Use recursion way to return itself
Usually Time Limit Exceed

int climbStairs(int n) {
    if (n <= 2)
        return n;
    else
        return climbStairs(n - 1) + climbStairs(n - 2);  // keep calling itself until the condition above is valid
}


### 2. DP Recursion
Use [Recursion](#1-Recursion) with dimensional programming by saving the element in an array
AC for sure

int value[46] = {0};

int climbStairs(int n) {
    if (n <= 2)
        return n;
    if (!value[n - 1])  // if the value in the previous one doesn't exist , make it exist
        value[n - 1] = climbStairs(n - 1) + climbStairs(n - 2);
    return value[n - 1];
}


### 3. For Loop
Use for to calculate the answer without returning itself
AC for sure but theoretically a bit faster than [DP Recursion](#2-DP-Recursion)

int climbStairs(int n) {
    int f[46] = {1, 1};
    for (int i = 2; i <= n; i++) {  // calculate the array's element to n
        f[i] = f[i - 1] + f[i - 2];
    }
    return f[n];
}


### 4. Permutations and Combinations
Use C(up, down) to calculate every conditions and sum the possibilities.
Uh... the awkward thing is that when it counts to 21!, long long can't fill the value.

long long C(int, int);
long long factorial(int);

int climbStairs(int n) {
    int sum = 0;
    for (int i = 0; i <= n / 2; i++) {
        sum += C(n - 2 * i, i);  // count all the ways to climb stairs
    }
    return sum;
}

long long C(int up, int down) {  // calculate combination
    return factorial(up + down) / (factorial(up) * factorial(down));
}

long long factorial(int a) {  // calculate factorial
    if (a == 0 || a == 1)
        return 1;
    else
        return factorial(a - 1) * a;
}