算法不难的话，也挺简单的哈-阿里云开发者社区

算法不难的话，也挺简单的哈

2022-04-29 97

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 算法不难的话，也挺简单的哈

题目

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