## 70. Climbing Stairs

###### tags: `Dynamic Programming` `Easy`

>[70. Climbing Stairs](https://leetcode.com/problems/climbing-stairs/description/)

<br>

:::info
:::spoiler *Optimal Space & Time Complexity*
<br>

- Time complexity: O()
- Space complexity: O()

:::

<br>

## Thoughts & Solutions

### YC
:::spoiler Code

// Time: O(n), Space: O(n)
var climbStairs = function(n) {
    if(n===1 || n===2) return n;
    
    //iteration
    const stairs=new Array(n);
    stairs[0] = 1;
    stairs[1] = 2;
    for(let i=2;i<n;i++){
        stairs[i] = stairs[i-1]+stairs[i-2];
    }
    return stairs[n-1];
};

:::

<hr/>

### Sol
:::spoiler Code

function helper(n, memo){
    if(n === 1 || n === 0) return 1;
    if(!(n in memo)) {
     memo[n] = helper(n-1, memo) + helper(n-2, memo) 
    }
    return memo[n];
}
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    const memo = {}
    return helper(n, memo)    
};

:::

<hr/>

### 東

1. Recursion with Time O(2^n) =>
2. Recursion with Memoization =>
3. Dynamic Programming with Array storing sequential result =>
4. Dynamic Programming Concept without array

Howard:
Solution 2 is also Dynamic Programming (top-down): **Memoization**
Solution 3, 4 is Dynamic progrmming (bottom-up): **Tabulation**
:::spoiler Code

// [Solution 1] Recursion
// Time O(2^n) | Space O(n)
var climbStairs = function(n) {
    if(n === 1) return 1;
    if(n === 2) return 2;
    return climbStairs(n-1) + climbStairs(n-2);
};

// [Solution 2] Recursion with Memoization
// Time O(n) | Space O(n)
var climbStairs = function(n, memoizeMap = {1 : 1, 2 : 2}) {
    if(memoizeMap.hasOwnProperty(n)) return memoizeMap[n];
    memoizeMap[n] = climbStairs(n-1, memoizeMap) + climbStairs(n-2, memoizeMap);
    return memoizeMap[n];
};

// [Solution 3] Dynamic Programming
// Time O(n) | Space O(n) (without call stack)
var climbStairs = function(n) {
    const dp = new Array(n).fill(0);
    dp[0] = 1;
    dp[1] = 2;

    for (let i = 2; i < n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }

    return dp[n-1];
};

// [Solution 4] Revised from Solution 3 without using array
// Time O(n) | Space O(1)
var climbStairs = function(n) {
    let prev = 1;
    let curr = 1;

    for (let i = 2; i <= n; i++) {
        [prev, curr] = [curr, prev + curr];
    }

    return curr;
};

:::

<hr/>

### Jessie

:::spoiler Code

:::

<hr/>

### Howard

:::spoiler Code

class Solution:
    def climbStairs(self, n: int) -> int:
        # subproblem: 到第n階的走法，是到第n-1的走法+到第n-2的走法
        # dp top down (memoization)
        # time O(n)
        # space O(n)
        self.memo = {}
        return self._climbStairs(n)

    def _climbStairs(self, n):
        if n == 1:
            return 1
        if n == 2:
            return 2
        if n in self.memo:
            return self.memo[n]
        
        self.memo[n-1] = self._climbStairs(n-1)
        self.memo[n-2] = self._climbStairs(n-2)
        return self.memo[n-1] + self.memo[n-2]

:::

<hr/>

### Haoyu

* [用Javascript實現階層與排列組合吧!](https://eruditeness.news.blog/2019/08/11/%E7%94%A8javascript%E5%AF%A6%E7%8F%BE%E9%9A%8E%E5%B1%A4%E8%88%87%E6%8E%92%E5%88%97%E7%B5%84%E5%90%88%E5%90%A7/)

// [1]
// 1
// c10

// [2]
// 1, 1
// 2
// c20 + c11

// [3]
// 1, 1, 1
// 2, 1
// 1, 2
// c30 + c21

// [4]
// 1, 1, 1, 1
// 2, 1, 1
// 1, 2, 1
// 1, 1, 2
// 2, 2

// [4/2, ..., 4]
// c40 + c31 + c22

// [5]
// 1, 1, 1, 1, 1
// 1, 2, 1, 1
// 1, 1, 2, 1
// 1, 1, 1, 2
// 2, 2, 1

// [5/2, ... ,5]
// c50 + c41 + c32

:::spoiler Code

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    function fraction(n) {
        let result = 1;

        while (n > 0) {
            result *= n;
            n -= 1;
        }

        return result;
    }


    function permutation (c, n){
        return fraction(c) / (fraction(n) * fraction(c - n));
    } 

    

    const maxTwoStep = (n - n % 2) / 2;

    let sum = 0;

    for (let i = 0; i <= maxTwoStep; i += 1) {
        const [countTotal, countTwoStep] = [n - i, i];

        sum = sum += permutation(countTotal, countTwoStep);
    }

    return sum;
};

:::

<hr/>

<br>

## Live Coding

:::spoiler (name)

// write your code here

:::