算法：10阶层楼梯，每次只能走一阶或两阶，问有多少种走法？

问题：10阶层楼梯，每次只能走一阶或两阶，问有多少种走法？

递归法

设F(n)是爬到n阶层的走法数，那么
F(10) = F(9) + F(8)
F(9) = F(8) + F(7)
...
F(3) = F(2) + F(1)
F(1) 为1中走法，F(2)为2种走法，故编程如下

int getClimbWays(int n) {
    if (n < 1) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    return getClimbWays(n - 1) + getClimbWays(n - 2);
}

计算结果是89种，通过该方法就可以计算任意阶层的走法。
复杂度分析：
时间复杂度：O(2ⁿ)，因为每次调用都会执行该方法两次。这个复杂度随着n的增大，执行时间会急剧增加，故需要优化。

这个方法的递归图如下

可以看到有很多重复的递归调用,我们可将已经计算的结果通过Hash表保存起来，如果需要时取出即可，这就称为备忘录算法

备忘录算法

class Solution {
    // 利用Hash表存储
    HashMap<Integer, Integer> map = new HashMap<>();
    int getClimbWays(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        if (map.containsKey(n)) {
            return map.get(n);
        }
        int value = getClimbWays(n - 1) + getClimbWays(n - 2);
        map.put(n, value);
        return value;
    }
}

复杂度分析：
时间复杂度：O(n),需要方法调用的只有F(1)->F(n)各一次
空间复杂度：O(n),HashMap种会存储n-2个数据，对于F(1)和F(2)不会存储

由于引入了HaspMap导致空间复杂度增大。我们是否可以继续优化？原问题可以拆分为小问题，然后求解，F(1) = 1,F(2) = 2,F(3) = F(1) + F(2) ... F(n) = F(n-2) + F(n-1),我们可以从最小问题入手，发现后面解时前面两个解的和，我们就可以采用迭代的方式的完成。这就是动态规划

动态规划

class Solution {
    int getClimbWays(int n) {
        if (n < 1) return 0;
        if (n == 1) return 1;
        if (n == 2) return 2;
        int a = 1;
        int b = 2;
        for (int i = 2; i < n; i++) {
            int temp = a + b;
            a = b;
            b = temp;
        }
        return b;
    }
}

复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)