題目

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

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

注意：給定 n 是一個正整數。

示例 1：

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

示例 2：

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

代碼（C語言）

方法1：遞歸

代碼可以，不過第34/45個測試用例的時候超出時間限制，考慮不用遞歸的做法，見方法2

int climbStairs(int n) {if(1==n){return 1;}if(2==n){return 2;}return climbStairs(n-1)+climbStairs(n-2); }

方法2：斐波那契數列

這道題是典型的斐波那契數列，f(n)=f(n-1)+f(n-2)

題目沒給n的范圍，先寫了個100試試，居然0ms通過了

int climbStairs(int n) {int a[100];int i;a[0]=0;a[1]=1;a[2]=2;for(i=3;i<100;i++){a[i]=a[i-1]+a[i-2];}return a[n]; }

總結

以上是生活随笔為你收集整理的leetcode 70. 爬楼梯（C语言）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。