[[433205]]

假設(shè)你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢?

注意： 給定 n 是一個正整數(shù)。

示例 1：

輸入： 2 
輸出： 2 
解釋： 有兩種方法可以爬到樓頂。 
1. 1 階 + 1 階 
2. 2 階 

示例 2：

輸入： 3 
輸出： 3 
解釋： 有三種方法可以爬到樓頂。 
1. 1 階 + 1 階 + 1 階 
2. 1 階 + 2 階 
3. 2 階 + 1 階 

解法：動態(tài)規(guī)劃

動態(tài)規(guī)劃(Dynamic Programming，DP)是一種將復雜問題分解成小問題求解的策略，但與分治算法不同的是，分治算法要求各子問題是相互獨立的，而動態(tài)規(guī)劃各子問題是相互關(guān)聯(lián)的。

分治，顧名思義，就是分而治之，將一個復雜的問題，分成兩個或多個相似的子問題，在把子問題分成更小的子問題，直到更小的子問題可以簡單求解，求解子問題，則原問題的解則為子問題解的合并。

我們使用動態(tài)規(guī)劃求解問題時，需要遵循以下幾個重要步驟：

• 定義子問題
• 實現(xiàn)需要反復執(zhí)行解決的子子問題部分
• 識別并求解出邊界條件

第一步：定義子問題

如果用 dp[n] 表示第 n 級臺階的方案數(shù)，并且由題目知：最后一步可能邁 2 個臺階，也可邁 1 個臺階，即第 n 級臺階的方案數(shù)等于第 n-1 級臺階的方案數(shù)加上第 n-2 級臺階的方案數(shù)

第二步：實現(xiàn)需要反復執(zhí)行解決的子子問題部分

dp[n] = dp[n−1] + dp[n−2] 

第三步：識別并求解出邊界條件

// 第 0 級 1 種方案  
dp[0]=1  
// 第 1 級也是 1 種方案  
dp[1]=1 

最后一步：把尾碼翻譯成代碼，處理一些邊界情況

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

復雜度分析：

• 時間復雜度：O(n)
• 空間復雜度：O(n)

優(yōu)化空間復雜度：

let climbStairs = function(n) { 
    let res = 1, n1 = 1, n2 = 1 
    for(let i = 2; i <= n; i++) { 
        res = n1 + n2 
        n1 = n2 
        n2 = res 
    } 
    return res 
} 

空間復雜度：O(1) 

leetcode：https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-wen-ti-by-user7746o/