題目來(lái)源：
https://leetcode.cn/problems/climbing-stairs/
題目：
假設(shè)你正在爬樓梯额各。需要 n 階你才能到達(dá)樓頂影钉。
每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢欲账？
示例：
示例 1：
輸入：n = 2
輸出：2
解釋：有兩種方法可以爬到樓頂巍实。
1. 1 階 + 1 階
2. 2 階
示例2:
輸入：n = 3
輸出：3
解釋：有三種方法可以爬到樓頂婉刀。
1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階
提示
1 <= n <= 45
找規(guī)律
1 2 3 5 8 13 ...
我們很容易想到斐波那契數(shù)列數(shù)列损话，使用遞歸
f(n) = f(n-1) + f(n-2)
然鵝：寫的時(shí)候很開心，提交的時(shí)候翎碑，執(zhí)行超時(shí)，因?yàn)閚的最大值為45之斯，使用遞歸計(jì)算量過(guò)大日杈，測(cè)試用例不通過(guò)
方案一：滑動(dòng)窗口
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
let result = 0
let begin = 1
let next = 2
if(n === 1) return 1
if(n === 2) return 2
for(let i = 3;i<=n;i++){
result = begin + next
// 滑動(dòng)后移
begin = next
next = result
}
return result
};
方案二：
使用動(dòng)態(tài)規(guī)劃：
//dr[i] 表示第幾節(jié)的方法數(shù)
let dp = [0,1,2]
for(let i = 3; i<= n; i++){
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
使用動(dòng)態(tài)規(guī)劃解題5步驟遣铝，即動(dòng)規(guī)五部曲：
定義一個(gè)一維數(shù)組來(lái)記錄不同樓層的狀態(tài)
1,確定dp數(shù)組以及下標(biāo)的含義(下標(biāo)的定義很重要):
dp[i]： 爬到第i層樓梯，有dp[i]種方法
2莉擒，確定遞推公式
dp[i] = dp[i - 1] + dp[i - 2]
3酿炸，dp數(shù)組如何初始化
let dp = [0,1,2]
4，確定遍歷順序
從遞推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出涨冀，遍歷順序一定是從前向后遍歷的
5填硕，舉例推導(dǎo)驗(yàn)證
舉例當(dāng)n為5的時(shí)候，dp table（dp數(shù)組）應(yīng)該是這樣的
