问题：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(2n)，因为每次调用都会执行该方法两次。这个复杂度随着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)
