leetcode70.爬楼梯

题目链接

解法一:递归求解

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)。