爬樓梯 3種方法比較

 1 /*
 2     假設你正在爬樓梯。需要 n 階你才能到達樓頂。
 3     每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？
 4 
 5     示例 1：
 6     輸入：n = 2
 7     輸出：2
 8     解釋：有兩種方法可以爬到樓頂。
 9     1.     1 階 + 1 階
10     2.     2 階
11 
12     示例 2：
13     輸入：n = 3
14     輸出：3
15     解釋：有三種方法可以爬到樓頂。
16     1.     1 階 + 1 階 + 1 階
17     2.     1 階 + 2 階
18     3.     2 階 + 1 階
19 */
20 
21 // 方法一：遞歸方法，類似遞歸形式的斐波那契數列，時間復雜度：O(2**n)，空間復雜度：O(n)
22 
23 // 方法二：記憶化遞歸方法，時間復雜度：O(n),O(n)
24 #include <iostream>
25 #include <cstdio>
26 using namespace std;
27 
28 int climbStairsMemo(int n, int memo[]) {
29     if (memo[n] > 0) {
30         return memo[n];
31     }
32     if (n == 1) memo[n] = 1;
33     else if (n == 2) memo[n] = 2;
34     else memo[n] = climbStairsMemo(n - 1, memo) + climbStairsMemo(n - 2, memo);
35     return memo[n];
36 }
37 
38 int climbStairs2(int n) {
39     int memo[n + 1];
40     return climbStairsMemo(n, memo);
41 
42 }
43 
44 
45 // 方法三：動態規劃，時間復雜度：O(n),O(n)
46 int climebStairs3(int n) {
47     if (n == 1) return 1;
48     int dp[n + 1];
49     dp[1] = 1;
50     dp[2] = 2;
51 
52     for (int i = 3; i <= n; i++) {
53         dp[i] = dp[i - 1] + dp[i - 2];
54     }
55 
56     return dp[n];
57 }
58 
59 // 方法四：
60 /*
61     可以發現，方法三在計算 dp[i] 時，實際上只需要用到 dp[i - 1] 和 dp[i - 2] 的值，并不需要存儲整個數組 dp。
62     因此，可以使用常數級的額外空間來優化這段代碼，將空間復雜度降低到 O(1)。以下是優化后的代碼：
63 */
64 int climbStairs4(int n) {
65     if (n == 1) return 1;
66     int first = 1;
67     int second = 2;
68     int third;
69 
70     for (int i = 3; i <= n; i++) {
71         third = first + second;
72         first = second;
73         second = third;
74     }
75 
76     return second;
77 }
78 
79 int main() {
80 
81 
82 
83     return 0;
84 }