试图理解这个动态规划 python 代码？

Question

所以我正在阅读这个优秀的 intro 动态规划，我正在尝试破译这个 python 代码（斐波那契数的 DP 方法）。我主要在 C/C# 中编写代码，所以我有点难以理解 Python。所以这是代码：

def fibonacciVal(n):
    memo = [0] * (n+1)
    memo[0], memo[1] = 0, 1
    for i in range(2, n+1):
        memo[i] = memo[i-1] + memo[i-2]
    return memo[n]

所以，我想了解的部分是：

memo = [0] * (n+1) : 我知道这是一个数组，但是值是如何存储在这里的，它是如何初始化的？
for i in range(2, n+1): : 为什么它循环到 n+1，不应该只循环到 n 吗？

就是这样。我正在尝试自己破译这个，有 python 经验的人在这里帮助我会有所帮助。

谢谢！

Answer 1

1: [0]*3 -> [0,0,0] i.e. multiplying an array duplicates it that many times -n+1 in your case-.
2: because you start with [0,1,0,0,0, ...]
 the first index you add to is ^

... the last index you add to will be at n+1 because the first index you added to was 2
[0,1,1,2,3,5,8,13,21,...]

Answer 2

您 "trying to understand" 使用什么工具？一些基本的 print 命令会有很大帮助：

def fibonacciVal(n):
    memo = [0] * (n+1)
    print("INIT", memo)
    memo[0], memo[1] = 0, 1
    for i in range(2, n+1):
        memo[i] = memo[i-1] + memo[i-2]
        print("TRACE", i, memo)
    return memo[n]

fibonacciVal(5)

输出：

INIT [0, 0, 0, 0, 0, 0]
TRACE 2 [0, 1, 1, 0, 0, 0]
TRACE 3 [0, 1, 1, 2, 0, 0]
TRACE 4 [0, 1, 1, 2, 3, 0]
TRACE 5 [0, 1, 1, 2, 3, 5]

Answer 3

memo = [0] * (n+1) : I get that this is an array, but how are the values being stored here, how is it being initialized?

当您将单元素列表乘以 Python 中的一个整数时，它会初始化一个列表，其中该元素会重复您指定的次数。例如，对于 n=5:

memo = [0] * (n+1)

会初始化一个6个0的列表，赋给变量memo.

>>> n = 5
>>> memo = [0] * (n+1)
>>> memo
[0, 0, 0, 0, 0, 0]

请注意，这种用于初始化列表的方法适用于不可变对象列表（布尔值、数字、字符串等），但不适用于可变对象（如列表列表或列表列表）字典）。这是因为 Python 将 相同对象 的 n 个副本添加到列表中，这通常不是您想要的。（当您尝试更改列表中的一个可变对象时，所有这些对象都会更改，因为它们都只是同一对象的副本。）

for i in range(2, n+1): : why is it looping till n+1, shouldn't it be till n only?

它确实在 n 处停止，因为这是 range 函数的内置行为。当你传入两个参数时，它们是它的 start 和 stop 值。 range函数将return从start（含）到stop（不含）的序列。

如果你说 range(2, n)，它会停在 n-1。（另一种思考方式是，将 n 加 1 使其停在 n。）

Answer 4

   dic ={}
    def febo (n):
    if n in dic:
        return dic[n]
    if n<=2:
        dic[n] = 1
    else:
        dic[n]  = febo(n-1) + febo(n-2)
    return dic[n]

    if __name__ == "__main__":
        n = int(input())
        print(febo(n))

##使用这个

试图理解这个动态规划 python 代码？

Trying to understand this dynamic programming python code?

python

dynamic-programming

fibonacci