Python中的记忆化

Question

我很想请你帮我理解一下在Python中使用记忆化（Memoization）的这个方法。我刚学Python，对这种语法还不是很明白。

def fib_mem(n):
    return fib_mem_helper(n,[0,1]+[-1]*(n-1))

def fib_mem_helper(i,mem):
    if mem[i] == -1:
        mem[i]=fib_mem_helper(i-1,mem) + fib_mem_helper(i-2,mem)
        return mem[i]

这是我看到的一段用记忆化计算斐波那契数的代码，[0,1]+[-1]*(n-1) 这是什么意思呢？能不能给我解释一下这种写法代表什么？

Answer 1

这段代码看起来有点奇怪，像是有语法错误。不过根据你的问题：

[0,1] 是一个包含两个元素的列表，第一个元素是整数0，第二个元素是整数1。

在Python中，使用记忆化技术来实现这样的一个函数，合理的写法应该是：

def fib(i):
    try:
        return fib._memory[i]
    except KeyError:
        pass
    if i == 1 or i == 2:
        return 1
    else:
        f = fib(i-1) + fib(i-2)
        fib._memory[i] = f
        return f
fib._memory = {}

Answer 2

[-1]*5 会创建一个新的列表，这个列表里有五个元素，都是 -1，也就是 [-1 -1 -1 -1 -1]。

[0 1]+[-1]*5 会把两个列表合并在一起，变成 [0 1 -1 -1 -1 -1 -1]。

Answer 3

[0, 1] + [-1] * (n - 1) 的意思是“把两个列表合在一起，一个是 [0, 1]，另一个是 -1 重复 n-1 次”。