欣迪

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

Constraints:

  • 1 <= n <= 45

解法一 數學公式

為了這個回頭去翻了高中數學

由於步數是由 1 和 2 步組成,所以我們可以很輕易的算出最步和最少步,再利用公式去逐個計算各種組成的方法。

缺點就是效能極差。

var climbStairs = function(n) {
    const max = Math.floor(n / 2)
    let total = 1
    for (let i = 1; i <= max; i++) {
        const steps = n - i
        let nTwoSteps = i
        let nOneSteps = n - (2*i)
        if (nOneSteps === 0 || nTwoSteps === 0) {
            total+= 1
            continue
        }
        
        let nSteps = steps
        for(let j = steps - 1; j >= 1; j--) {
            nSteps *= j
        }
        for(let j = i - 1; j >= 1; j--) {
            nTwoSteps *= j
        } 
        for(let j = n - (2*i) - 1; j >= 1; j--) {
            console.log(nOneSteps, j, typeof nOneSteps)
            nOneSteps *= j
        } 
    
        total += nSteps / (nTwoSteps * nOneSteps)
        
    }
    return total
};

解法二 費氏數列

後來去看了討論區,結果這題的結果會符合費波那契數

var climbStairs = function(n, memo = {1:1, 2:2}) {
   if (memo[n] !== undefined) return memo[n];   
   memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo);
   return memo[n];
};

訂閱 IT-Monk

訂閱最新文章的發布消息! 😚😚😚
Loading

作者介紹 - 欣迪

欣迪

從設計到寫程式,發現自己有追求前端技巧的自虐傾向。不斷的踩坑,再從坑裡爬出來,慢慢對攀岩有點心得。 目前在多間公司擔任網站設計顧問。 同時也是網站架設公司負責人。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。