递归,但是用Python3递归时可以加装饰器:@functools.lru_cache()
这是一个缓存工具,可以把之前算过的一些函数保存下来,加速程序运行.
本题不加这个装饰器会超时.
其实加了这个装饰器以后,是O(n)的时间复杂度,不加的话就由于函数会重复调用,时间开销更大.
import functools class Solution(object): @functools.lru_cache() def climbStairs(self, n): """ :type n: int :rtype: int """ if n==0:return 0 if n==1:return 1 if n==2:return 2 return self.climbStairs(n-1)+self.climbStairs(n-2)
原文：https://www.cnblogs.com/zywscq/p/10568325.html