動的計画法とフィボナッチ数列

Question

###質問
フィボナッチ数列において101番目の数字を動的計画法を用いて求めることにしたのですが、メモリストdpの要素数がnだと動かないのはなぜでしょうか。
###該当のソースコード

n = int(input()) #n = 100を考える
dp = [-1 for i in range(n+1)] # range(n)だと動かない

def fib_dp(n): #解答が出る
    if n == 0:
        rec = 0
    elif n == 1:
        rec = 1
    elif dp[n] != -1:
        return dp[n]
    else:
        rec = fib_dp(n-1) + fib_dp(n-2)
    dp[n] = rec
    return rec

def fib(n): #タイムアウトする
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

print(fib_dp(n))

Answer 1

質問に上げていただいているソースコードでは n番目のフィボナッチ数をそのまま dp[n] に格納するようにコーディングされております。

しかしながら range(n) で配列を作成してしまうと、配列サイズが n となるので、(n-1)番目までのフィボナッチ数までしか格納できません。(__index__値は0から始まるので)

配列サイズを (n+1) としているのはその為かと思われます。