题目描述：给正整数 n 表示楼梯级数，每次能迈一层或者两层，问一共有多少种登顶法。
分析：基础的常见题，两种思路三种做法。到达第 n 级台阶的方法为 n - 1 级登一步，或n - 2 级登两步。递归或迭代，递归肯定要超时，迭代时间复杂度O(n)，空间O(1)。第三种数学法，这个规律实际上是斐波那契数列的递推式，可以用斐波那契通项公式:
迭代法：时间复杂度O(n)，空间O(1)。
class Solution {
public:
int climbStairs(int n) {
if (n == 1 || n == 0) return 1;
int a = 0, b = 1;
for (int i = 1; i <= n; i ++)
{
int t = b;
b += a;
a = t;
}
return b;
}
};
迭代法二：时间复杂度O(n)，空间O(n)
class Solution {
public:
int climbStairs(int n) {
vector<int> f(n + 1, 0);
f[0] = 1;
f[1] = 2;
for (int i = 2; i <= n; i++)
f[i] = f[i - 1] + f[i - 2];
return f[n];
}
};
记忆化搜索：
#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
using namespace std;
int f[100];
int fun(int x)
{
if (x == 1 || x == 0) return 1;
if (f[x] != 0) return f[x];
f[x] = fun(x - 1) + fun(x - 2);
return f[x];
}
int main()
{
f[0] = 1;
f[1] = 1;
cout<< fun(10)<<endl;
return 0;
}
斐波那契公式：时间复杂度O(1)，空间O(1)。
class Solution {
public:
int climbStairs(int n) {
double x = sqrt(5);
return floor( ( pow( (1 + x) / 2, n + 1) + pow( (1 - x) / 2, n + 1) ) / x + 0.5 );
}
};
