每日算法:爬樓梯問題
每日算法:爬樓梯問題
動態規劃(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/