cachedecorator

简要介绍python的decorator：cache

先看一个经典题：https://leetcode.cn/problems/minimum-number-of-days-to-eat-n-oranges/description/

上来直接记忆化指数下降搜索得到代码：

ans = {
	1:1,
	# ...
}
def rec(n):
    if n in ans.keys():
        return ans[n]
    else:
        return min(n % 2 + rec(n // 2), n % 3 + rec(n // 3)) + 1

但这里其实不必手动记忆化，直接用python自带的@cache即可（LRU，比直接全部存储高明）：

@cache
def rec(n):
    if n <= 1:
        return 1
    else:
        return min(n % 2 + rec(n // 2), n % 3 + rec(n // 3)) + 1

实测后者比前者快一些。