Пытаетесь понять этот динамический программный код Python?

Question

Итак, я читаю это превосходное введение в Динамическое программирование, и я пытаюсь расшифровать этот код питона (подход 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]

Итак, биты, которые я пытаюсь понять:

1. memo = [0] * (n + 1): Я понял, что это массив, но как здесь хранятся значения, как он инициализируется?

2. для i в диапазоне (2, n + 1): почему это циклично до n + 1, не должно ли быть только до n?

Вот и все. Я пытаюсь расшифровать это сам, и это помогло бы мне помочь кому-то с опытом работы с Python.

Спасибо!

Answer 1

Какие инструменты вы используете для «попыток понять»? Несколько базовых 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 2

memo = [0] * (n+1): Я понял, что это массив, но как здесь хранятся значения, как он инициализируется?

Когда вы умножаете одноэлементный список на целое число в 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):: почему он зацикливается до n + 1, не должен ли он быть до n только?

Он останавливается на n, поскольку это встроенное поведение функции range. Когда вы передаете два аргумента, они являются его значениями start и stop. Функция range возвращает последовательность от start (включительно) до stop (исключая).

Если бы вместо этого вы сказали range(2, n), он остановился бы на n-1. (Еще один способ думать об этом - добавление 1 к n - это то, что останавливает его на n.)

Answer 3

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,...]