题目
假设你正在爬楼梯，需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶，你有多少种不同的方法可以爬到楼顶呢？
难度：⭐
解法1：暴力递归
难度：⭐
优点：代码简洁优雅
缺点：对空间消耗较大，因此要好好考虑是不是真的适合使用递归来解决问题
class Solution { public int climbStairs(int n) { if(n == 1) return 1; if(n == 2) return 2; return climbStairs(n-1) + climbStairs(n-2); } }
解法2：递归优化
难度：⭐⭐
由于第一种方法有多余的计算，是没有必要的，因此可以优化，我的方案是使用map集合来存储计算过的值，每次计算时判断一下是否在集合中已经有了，有了就直接取出对应的 value ，这样就好多了。
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; } } }
解法3：循环解决
难度：⭐⭐⭐
自底向上，累加计算，很简单，也很好理解 ！！！
class Solution { public int climbStairs(int n) { int result = 0; int pre = 2; int prePre = 1; if(n == 1) return prePre; if(n == 2) return pre; for(int i = 3;i<=n;i++){ result = pre + prePre; prePre = pre; pre = result; } return result; } }
