Python 记忆化导致的 Memory Limit Exceeded

Python 3.9 中引入了一个新的装饰器 functools.cache 用来做缓存，刷到 DP 相关的题目，就可以很方便地做记忆化了：

 1class Solution:
 2    def maximumScore(self, nums: List[int], multipliers: List[int]) -> int:
 3        N, M = len(nums), len(multipliers)
 4
 5        @cache
 6        def dp(left: int, right: int) -> int:
 7            i = N - (right - left + 1)
 8            if i == M:
 9                return 0
10            if left == right:
11                return nums[left] * multipliers[i]
12            return max(
13                nums[left] * multipliers[i] + dp(left + 1, right),
14                nums[right] * multipliers[i] + dp(left, right - 1),
15            )
16
17        return dp(0, N - 1)

不需要再手动地维护缓存，但是需要注意的是，被装饰的方法的参数要求可以被 hash，因为要作为 key。

在 LeetCode #1770. Maximum Score from Performing Multiplication Operations 这道题中，遇到了一个超内存的错误。

LeetCode 在运行测试用例的时候，不会多次创建 Solution 对象，只会用同一个对象去跑所有的用例，那么这里的缓存自然是所有用例的缓存了，但是我们只需要对当前用例缓存，之前的就可以清空了。

所以总的空间占用，对应消耗空间最大的那一个测试用例，而不再是所有测试用例总共的空间占用。

装饰器提供了一个方法 cache_clear() 用来清空缓存，那么在 return 之后清空就可以了：

1try:
2    return dp(0, N - 1)
3finally:
4    dp.cache_clear()

记忆化导致超内存，并不是所有测试用例的缓存，都存在了同一个地方。 使用 id(dp) 可以看到每个测试用例都是不一样的 dp 对象，只是之前的缓存没有被回收而已。

这有点类似于按层遍历二叉树，如果维护一个当前层的 List 作为中间变量，那么其实空间复杂度是 O(N)，因为每一层都创建了一个 List 对象，推荐的做法是使用双端队列 Deque，理论上来说复杂度是 O(N/2) 还是 O(N)，但是最大空间占用是最长的一层的节点数量，通过左 pop 和右 append，不会出现分配完用一次就扔掉的浪费了。

另一个题外话，同样因为 LeetCode 使用同一个对象来运行所有的测试用例，维护一个全局变量，比如类的静态变量，可能会遇到上一个用例遗留脏数据的问题。

可以尝试用其他方式存信息，或者每次都要手动清空了，代码会稍微丑陋一点。