浅谈：算法中的斐波那契数（四）

方法三：记忆化自顶向下的方法

我们先计算存储子问题的答案，然后利用子问题的答案计算当前斐波那契数的答案。我们将递归计算，但是通过记忆化不重复计算已计算的值。

算法：

• 如果 N <= 1，则返回 N。
• 调用和返回 memoize(N)。
• 如果 N 对应的斐波那契数存在，则返回。
• 否则将计算 N 对应的斐波那契数为 memoize(N-1) + memoize(N-2)。

Java 实现

class Solution { private Integer[] cache = new Integer[31]; public int fib(int N) { if (N <= 1) { return N; } cache[0] = 0; cache[1] = 1; return memoize(N); } public int memoize(int N) { if (cache[N] != null) { return cache[N]; } cache[N] = memoize(N-1) + memoize(N-2); return memoize(N); } }

Python 实现

class Solution: def fib(self, N: int) -> int: if N <= 1: return N self.cache = {0: 0, 1: 1} return self.memoize(N) def memoize(self, N: int) -> {}: if N in self.cache.keys(): return self.cache[N] self.cache[N] = self.memoize(N-1) + self.memoize(N-2) return self.memoize(N)

复杂度分析