每日算法：爬樓梯問題
每日算法：爬樓梯問題
動態規劃(Dynamic
Programming，DP)是一種將復雜問題分解成小問題求解的策略，但與分治算法不同的是，分治算法要求各子問題是相互獨立的，而動態規劃各子問題是相互關聯的。
假設你正在爬樓梯。需要
n 階你才能到達樓頂。
每次你可以爬 1
或 2 個台階。你有多少種不同的方法可以爬到樓頂呢?
注意： 給定 n 是一個正整數。
示例 1：
1. 輸入： 2
2. 輸出： 2
3. 解釋： 有兩種方法可以爬到樓頂。
4. 1. 1 階 + 1 階
5. 2. 2 階
示例 2：
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/