假设你正在爬楼梯。需要 n 阶你才能到达楼顶
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
自我解答：
1和2的组合有特别多种，我尝试凑出通项公式来，但凑了好久都没有凑出。后来突然想到，
爬楼梯，每次都可以选择爬1阶或着2阶，这其实就如同二叉树一样，两个孩子分别是 n-1，n-2,
那应该可以用二叉树遍历的方式进行，统计所有叶子节点数就可以了。但是在这个“二叉树”的遍历过程中，
其实会遇到很多重复的问题：如 n = 4, 分成 3, 2; 之后 3 又分成 2, 1; 这里 2就重复了。
为此，可以添加一个缓存。通过学习《算法导论》得知，这其实就是动态规划的一种实现方法：
带备忘的自顶向下法(top-down with mermoization)
class Solution4:
def __init__(self):
self.cache = {1: 1, 2: 2}
def climbStairs(self, n: int) -> int:
if n in self.cache:
return self.cache[n]
num = self.climbStairs(n - 1) + self.climbStairs(n - 2)
self.cache[n] = num
return num
官方题解
也是动态规划，此类问题除了“带备忘的自顶向下法”，还有“自底向上法”。自顶向下的过程中，
把每个问题(n)都分成了两个更小的子问题(n-1, n-2)，可以跳出二叉树的框架，既然每个问题
都有依赖的子问题，那么就有一个最小的子问题，这个最小的子问题是很容易推算出来并设置成常
量的，如这里最小的子问题是 f(1) = 1 和 f(2) = 2, 那么 f(3) = f(1) + f(2),
f(4) = f(2) + f(3)..., 可以一路向上求解父问题，这样的方式每个问题所依赖的两个子问题都
已知，直接用就可以了，由此得到最终解。
class Solution2:
def climbStairs(self, n: int) -> int:
if n == 1: return 1
if n == 2: return 2
case_nums = [0 for x in range(n + 1)]
case_nums[1], case_nums[2] = 1, 2
for i in range(3, n + 1):
case_nums[i] = case_nums[i - 1] + case_nums[i - 2]
return case_nums[n]
优化：每次计算问题，其实都只需要知道两个子问题的解就行了，因此，其实不需要使用一个map来记录
所有子问题的解，只需要使用两个变量记录两个子问题就行了。
class Solution5:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
a, b = 1, 2
for i in range(2, n):
a, b = b, a + b
return b