【leetcode】爬楼梯（@lru_cache()装饰器用法）

忘是亡心i 2022-02-26 21:18 112阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]  
自己的解法，直接使用动态规划，比较简单

class Solution:
        def climbStairs(self, n: int) -> int:
            if n == 1:
                return 1
            memory = [0] * (n + 1)
            memory[1] = 1
            memory[2] = 2
            for i in range(3, n + 1):
                memory[i] = memory[i - 1] + memory[i - 2]
            return memory[n]

--------------------

## @lru\_cache装饰器 ##

from functools import lru_cache
    
    class Solution:
        @lru_cache(10**8)
        def climbStairs(self, n):
            if n == 1:
                return 1
            elif n == 2:
                return 2
            else:
                return self.climbStairs(n - 1) + self.climbStairs(n - 2)

可以看到，这个cache是从functools里面import lru\_cache  
参考链接：[https://zhuanlan.zhihu.com/p/27643991][https_zhuanlan.zhihu.com_p_27643991]  
![在这里插入图片描述][20190326114954505.png]  
这个装饰器实现了备忘的功能，是一项优化技术，把耗时的函数的结果保存起来，避免传入相同的参数时重复计算。lru 是（least recently used）的缩写，即最近最少使用原则。表明缓存不会无限制增长，一段时间不用的缓存条目会被扔掉。  
这个装饰器支持传入参数，还能有这种操作的？maxsize 是保存最近多少个调用的结果，最好设置为 2 的倍数，默认为 128。如果设置为 None 的话就相当于是 maxsize 为正无穷了。还有一个参数是 type，如果 type 设置为 true，即把不同参数类型得到的结果分开保存，如 f(3) 和 f(3.0) 会被区分开。

有了缓存之后，追踪次数会明显减少，不会调用递归。  
![在这里插入图片描述][20190326115348832.png]  
两种方法都是通过的

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]: /images/20220227/67304104e5554dff88d208d9405c4f87.png
[https_zhuanlan.zhihu.com_p_27643991]: https://zhuanlan.zhihu.com/p/27643991
[20190326114954505.png]: /images/20220227/3fcb4715585446ecbe1078f76e4df167.png
[20190326115348832.png]: /images/20220227/3d207e738f594c9e8369a28f23945001.png