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

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

示例 1：

輸入：n = 2
輸出：2
解釋：有兩種方法可以爬到樓頂。
1. 1 階 + 1 階
2. 2 階

示例 2：

輸入：n = 3
輸出：3
解釋：有三種方法可以爬到樓頂。
1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階

提示：

• 1 <= n <= 45

代碼：

int climbStairs(int n) { // leeCode 70.爬樓梯if (n == 1)return 1;if (n == 2)return 2;// 最后一步只有兩種可能，跨1步或跨2步，這兩種可能看作為互斥事件，將這倆種走法方法數加起來就是答案。// 設爬到n層階梯所需方法數為f(n)// 先跨到n-1層，再從n-1層跨1層到n層，方法數為f(n - 1)； 同理先跨到n-2層，再從n-2層直接跨2層到n層，方法數為f(n - 2)// 因為這倆種方案互斥，所以f(n) = f(n-1) + f(n-2);// f(1) = 1， f(2) = 2, 可以根據f(1)、f(2)的值算出f(3),同理可以再算出f（4）..., 一直算出f(n)int* f = (int*)malloc((n + 1) * sizeof(int)); // 需要求f[n], 所以數組有n + 1個元素if (f == NULL) {printf("malloc, error happend");return 0;}memset(f, 0, sizeof(f)); // 注意：設置的值會轉化為 unsigned char ，int數組可以這樣初始化0，其他值不要這么設置。*(f + 1) = 1;*(f + 2) = 2;for (int i = 3; i <= n; i++) {*(f + i) = *(f + i - 1) + *(f + i - 2);}int res = *(f + n);free(f);return res;
}

?測試代碼：

void testLeeCode70() {int n;printf("請輸入臺階數: ");int res = scanf_s("%d", &n); // scanf函數不安全，這里用scanf_s函數if (res == 1) { // 一個參數獲取到值printf("%d\n", climbStairs(n));}else {printf("輸入不符合預期");}	
}

打印結果：

ok

提交到LeeCode：

內存偏高，只擊敗5%，有點尷尬😂，可能是因為是用數組存儲 f(n)函數各個參數對應的函數值，可以優化為只用幾個變量，減少內存消耗，memset(f, 0, sizeof(f)) 這句代碼也多余。 代碼略。