这个题目是这样的，如果一次可以向上移动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
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/22259926/viewspace-2676927/ ，如需转载，请注明出处，否则将追究法律责任。
请登录后发表评论
登录
全部评论
