###動的計画法・メモ化再帰
フィボナッチ数列
# フィボナッチ数列
def fibo(n,memo):
# ベースケース
if n == 0:
return 0
elif n == -1:
return 1
# メモをチェック(既に計算済みなら答えをリターンする)
if memo[n] != -1:
return memo[n]
# 答えをメモしながら再帰呼び出し
memo[n] = fibo(n-1,memo) + fibo(n-2,memo)
return memo[n]
# メモ用配列(-1は未計算であることを表す)
memo = [-1] * 50
for n in range(50):
print(str(n) + "項目の値:" + str(fibo(n,memo)))
出力結果
0項目の値:0
1項目の値:1
2項目の値:1
3項目の値:2
4項目の値:3
5項目の値:5
6項目の値:8
7項目の値:13
8項目の値:21
9項目の値:34
10項目の値:55
11項目の値:89
12項目の値:144
13項目の値:233
14項目の値:377
15項目の値:610
16項目の値:987
17項目の値:1597
18項目の値:2584
19項目の値:4181
20項目の値:6765
21項目の値:10946
22項目の値:17711
23項目の値:28657
24項目の値:46368
25項目の値:75025
26項目の値:121393
27項目の値:196418
28項目の値:317811
29項目の値:514229
30項目の値:832040
31項目の値:1346269
32項目の値:2178309
33項目の値:3524578
34項目の値:5702887
35項目の値:9227465
36項目の値:14930352
37項目の値:24157817
38項目の値:39088169
39項目の値:63245986
40項目の値:102334155
41項目の値:165580141
42項目の値:267914296
43項目の値:433494437
44項目の値:701408733
45項目の値:1134903170
46項目の値:1836311903
47項目の値:2971215073
48項目の値:4807526976
49項目の値:7778742049