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];
};
