这个题目是这样的，如果一次可以向上移动1格或者2格，给出一定格数的梯子，有多少种移动方法可以刚好到顶。
比如给出2格梯子，有两种方法，一个是 1->1；还有是 一次 走2 格；
给出3格梯子，有三种方法，一个是1->1->1; 还有1->2, 还有2->1。
这个题目看起来好像很复制的样子，分析下，其实本质就是一个斐波拉契数组，一个n格的梯子方法数，可以是n-1 和n-2 的方法数之和。
代码也就很简单了，递归既可以，这里使用一个课程中提到的针对递归提速的缓存字典技巧；因为在递归分解时候，往往很多分解计算要跑很多次，把第一次的结果放在一个字典里面缓存使用可以大大提高速度。在实际使用中，可以使用functools.lru_cache这样工具，用装饰器形式更快捷的实现。实际提交代码后，显示运行速度也是超过85%的结果。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
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 |
原文：https://www.cnblogs.com/chenguopa/p/15239860.html