这个题目是这样的，如果一次可以向上移动1格或者2格，给出一定格数的梯子，有多少种移动方法可以刚好到顶。

比如给出2格梯子，有两种方法，一个是 1->1；还有是 一次 走2 格；

给出3格梯子，有三种方法，一个是1->1->1; 还有1->2, 还有2->1。

这个题目看起来好像很复制的样子，分析下，其实本质就是一个斐波拉契数组，一个n格的梯子方法数，可以是n-1 和n-2 的方法数之和。

代码也就很简单了，递归既可以，这里使用一个课程中提到的针对递归提速的缓存字典技巧；因为在递归分解时候，往往很多分解计算要跑很多次，把第一次的结果放在一个字典里面缓存使用可以大大提高速度。在实际使用中，可以使用functools.lru_cache这样工具，用装饰器形式更快捷的实现。实际提交代码后，显示运行速度也是超过85%的结果。

class Solution:
    cacheTable = {}
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        elif n == 2:
            return 2
        else:
            if n in self.cacheTable.keys():
                return self.cacheTable[n]
            else:
                stepCount = self.climbStairs(n-1) + self.climbStairs(n-2)
                self.cacheTable[n] = stepCount
                return stepCount