每日算法:爬樓梯問題

2021.11.04

每日算法:爬樓梯問題

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


假設你正在爬樓梯。需要 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 ProgrammingDP)是一種將復雜問題分解成小問題求解的策略,但與分治算法不同的是,分治算法要求各子問題是相互獨立的,而動態規劃各子問題是相互關聯的。

 

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

 

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

 

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

 

第一步:定義子問題

如果用 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)

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