LeetCode 精选100题-70题爬楼梯

题目描述：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

思路：

1. 第一阶楼梯：n =1，有一种方法 f(1)=1;
2. 第二阶楼梯：n =2，有两种方法 f(2)=2;
3. 当我们第一步爬了1个台阶时，我们可以有f(n-1)种方法爬到楼顶；
4. 当我们第一步爬了2个台阶时，我们可以有f(n-2)种方法爬到楼顶；
5. 第一步要么1个台阶要么2个台阶，所以我们共有方法：f(n)=f(n-1)+f(n-2) n>=3。

题解一（递归算法）：

代码实现：

class Solution {
    public int climbStairs(int n) {
         if(n==1) return 1;
        if(n==2) return 2;

        return climbStairs(n-1) +climbStairs(n-2);
        }
}

运行通过，但是这种方法时间复杂度为O（n²），超出时间限制。

我们随便分析一个数字 n=6：

其中一些数字不止算了一遍，我们可以选择map集合，以n为Key，算出的值放入map的Value，计算值时先看是否存在已计算过的值，若没有去计算，放入map。

class Solution {
    private Map<Integer,Integer> map =new HashMap();
    public int climbStairs(int n) {
        if(n==1) return 1;
        if(n==2) return 2;
        if(null != map.get(n)){
            return map.get(n);
        }else{
            int result = climbStairs(n-1) +climbStairs(n-2);
            map.put(n,result);
            return result;
        }

    }
}

题解二：

还是这张图：

1. f(3)和f(2)可以得到 f(4)；
2. f(4)和f(3)可以得到 f(5);
3. f(5)和f(4)可以得到 f(6);

......

class Solution {
		public int climbStairs(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;

        int pre = 2;
        int prePre = 1;
        int result = 0;
        for(int i=3;i<=n;++i){
            result = pre + prePre;
            prePre =pre;
            pre=result;

        }
        return result;
    }
  }