題目描述

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

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

注意： 給定 n 是一個正整數(shù)。

示例 1:

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

示例 2:

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

解題思路

動態(tài)規(guī)劃

1. 定義狀態(tài)： 設 dp[i] 表示爬到第 i 階樓梯的方法數(shù)。
2. 狀態(tài)轉(zhuǎn)移方程： dp[i] = dp[i-1] + dp[i-2]，即爬到第 i 階樓梯的方法數(shù)等于爬到第 i-1 階樓梯的方法數(shù)加上爬到第 i-2 階樓梯的方法數(shù)。
3. 初始狀態(tài)： dp[1] = 1，dp[2] = 2。
4. 遍歷順序： 從小到大遍歷，計算每一層樓梯的方法數(shù)。

特殊案例

• 如果輸入 n 為 1 或 2，則直接返回 n。

C#代碼實現(xiàn)

public int ClimbStairs(int n) {// 如果樓梯只有一階或者兩階，直接返回階數(shù)if (n == 1 || n == 2) {return n;}// 創(chuàng)建一個數(shù)組，長度為n+1int[] dp = new int[n + 1];// 初始化數(shù)組，第一階和第二階的步數(shù)都為1dp[1] = 1;dp[2] = 2;// 從第三階開始，動態(tài)規(guī)劃計算步數(shù)for (int i = 3; i <= n; i++) {// 動態(tài)規(guī)劃轉(zhuǎn)移方程，dp[i] = dp[i - 1] + dp[i - 2]dp[i] = dp[i - 1] + dp[i - 2];}// 返回最后一步的步數(shù)return dp[n];
}

C代碼實現(xiàn)

int climbStairs(int n) {// 如果樓梯只有一階或者兩階，直接返回階數(shù)if (n == 1 || n == 2) {return n;}// 定義一個數(shù)組，用來存儲階數(shù)對應的斐波那契數(shù)int* dp = (int*)malloc(sizeof(int) * (n + 1));// 初始化數(shù)組，斐波那契數(shù)從1開始，所以dp[1]和dp[2]都等于1dp[1] = 1;dp[2] = 2;// 從第三階開始，斐波那契數(shù)等于前兩階的和for (int i = 3; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}// 返回斐波那契數(shù)int result = dp[n];// 釋放內(nèi)存free(dp);return result;
}

時間復雜度和空間復雜度

• 時間復雜度：O(n)，其中 n 是樓梯的階數(shù)。需要計算每一層樓梯的方法數(shù)。
• 空間復雜度：O(n)。使用了一個大小為 n+1 的數(shù)組來保存中間結(jié)果。