解法一:递归求解
class Solution {
public int climbStairs(int n) {
if(n == 1){
return 1;
}
if(n == 2){
return 2;
}
return climbStairs(n - 1) + climbStairs(n - 2);
}
}
通过分析不难得到结论：爬到第n级台阶的方法实质只有两种：爬到第n-1级台阶再向上爬一级台阶，或者在第n-2级台阶再向上爬两级台阶。所以，爬到第n级台阶的方法总数为爬到第n-1级台阶的方法数加上爬到第n-2级台阶的方法数的和。
时间复杂度分析：
同斐波那契数列一样，如果使用递归调用，那么递归调用树如下：
可以分析得：该算法的时间复杂度为O(2 ^ n)；所以很显然，这种代码写法虽然优美，但是通不过OJ的时间限制。
解法二：将递归转换为非递归
class Solution {
public int climbStairs(int n) {
int method1 = 1;
int method2 = 2;
if(n == 1){
return method1;
}
if(n == 2){
return method2;
}
int res = 0;
for(int i = 3;i <= n;i++){
res = method1 + method2;
method1 = method2;
method2 = res;
}
return res;
}
}
将递归转换为非递归其实写法也比较简单，另外这种方法也优于动态规划，因为动态规划还要去开辟一个数组，额外空间复杂度为O(n),而这种写法的时间复杂度为O(n),额外空间复杂度为O(1)。
