假設(shè)你正在爬樓梯。需要 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 階
C
若用傳統(tǒng)遞歸或者Fibonacci遞歸會超時。
int climbStairs(int n){
int *a = (int *)malloc(sizeof(int)*(n+1));
a[0] = 1;
a[1] = 1;
for(int i = 2; i <= n; i++) {
a[i] = a[i - 1] + a[i - 2];
}
return a[n];
}
C++
class Solution {
public:
int climbStairs(int n) {
int *a = new int [n + 1];
a[0] = 1;
a[1] = 1;
for(int i = 2; i <= n; i++) {
a[i] = a[i - 1] + a[i - 2];
}
return a[n];
}
};
