题目
假设你正在爬楼梯,需要 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; } }