每日算法：爬樓梯問題

每日算法：爬樓梯問題

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

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

 

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

 

注意： 給定 n 是一個正整數。

 

示例 1：

1. 輸入： 2

2. 輸出： 2

3. 解釋： 有兩種方法可以爬到樓頂。

4. 1. 1 階 + 1 階

5. 2. 2 階

示例 2：

 1.輸入： 3

2. 輸出： 3

3. 解釋： 有三種方法可以爬到樓頂。

4. 1. 1 階 + 1 階 + 1 階

5. 2. 1 階 + 2 階

6. 3. 2 階 + 1 階

 

解法：動態規劃

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

 

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

 

我們使用動態規劃求解問題時，需要遵循以下幾個重要步驟：

 

• 定義子問題
• 實現需要反复執行解決的子子問題部分
• 識別並求解出邊界條件

 

第一步：定義子問題

如果用 dp[n] 表示第 n 級台階的方案數，並且由題目知：最後一步可能邁 2 個台階，也可邁 1 個台階，即第 n 級台階的方案數等於第 n-1 級台階的方案數加上第 n-2 級台階的方案數

 

第二步：實現需要反复執行解決的子子問題部分

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

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

// 第 0 級 1 種方案 

dp[0]=1 

// 第 1 級也是 1 種方案 

dp[1]=1

 

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

1. let climbStairs = function(n) {

2.   let dp = [1, 1]

3.    for(let i = 2; i <= n; i++) {

4.        dp[i] = dp[i - 1] + dp[i - 2]

5.     }

6.    return dp[n]

7. }

複雜度分析：

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

 

優化空間複雜度：

1. let climbStairs = function(n) {

2.    let res = 1, n1 = 1, n2 = 1

3.    for(let i = 2; i <= n; i++) {

4.        res = n1 + n2

5.        n1 = n2

6.        n2 = res

7.     }

8.   return res

9. }

空間複雜度：O(1)

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