[数据结构与算法]简单的算法：爬楼梯问题

题目

????????假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

解法

递归解法

public int calc(int reside) {
    if (reside == 1 || reside == 2) {
        return reside;
    }
    return calc(reside - 1) + calc(reside - 2);
}

????????可以完成任务，但是在力扣中提交会超时。本地执行一下超时的45，可不慢吗，3秒钟才执行完。

????????看到力扣的大神说加个Map缓存就好了。嗯，我再试试

Map<Integer, Integer> map = new HashMap<Integer, Integer>();

public int calc(int reside) {
    if (map.get(reside) != null) {
        return map.get(reside);
    } else {
        if (reside == 1 || reside == 2) {
            return reside;
        }
        int step_1 = calc(reside - 1);
        int step_2 = calc(reside - 2);
        map.put(reside - 1, step_1);
        map.put(reside - 2, step_2);
        return step_1 + step_2;
    }
}

????????嗯，确实解决了

数学公式解法

????????这个我看到了解题思路我人傻了，给大家截个图看看

? ? ? ? ?对于数学不好的我来说，确实很难想到了

动态规划解法

????????在考虑第x阶是怎么爬上来的情况时，分为两种情况，一种是爬1阶上来的，一种是爬2阶上来的。那么f(x) = f(x - 1) + f(x - 2)。递归解法中也是这么写的。

????????已知f(1) = 1。在循环中累加。代码如下

public int calc(int reside) {
    int p = 0, q = 0, r = 1;
    for (int i = 1; i <= reside; ++i) {
        p = q;
        q = r;
        r = p + q;
    }
    return r;
}

与50位技术专家面对面

20年技术见证，附赠技术全景图