leetcode70. 爬楼梯
针对这题，实际我们可以对其理解为：
对于每两个阶梯要么走1阶，要么走2阶。
解答一（超时）：
class Solution {
public int climbStairs(int n) {
if (n <= 2) {
return n;
}
return climbStairs(n - 1) + climbStairs(n - 2);
}
}问题在于，会存在重复计算的值，如图：
运行结果
解答二：
针对重复计算的问题，我们对其使用HashMap存储，如果再次计算时，直接从HashMap中取即可。
HashMap要放到递归方法外，否则不是同一个对象，全不走存储，会超出时间限制。
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;
}
}
}
解答三：
由底向上叠加
class Solution {
public int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
int result = 0;
int prePre = 1;
int pre = 2;
for (int i = 3; i <= n; i++) {
result = prePre + pre;
prePre = pre;
pre = result;
}
return result;
}
}
