DA:dp

フィボナッチ数列

次のコードは，再帰関数を用いた全探索による解法です．ただし，fibonacci 関数の引数 n は正の整数であることを仮定しています．

def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(10))

しかしこれは無駄が多い実装です．fobonacci(n) を実行する際に，fibonacci(n-1) と fibonacci(n-2) が実行されますが，fibonacci(n-1) の中でも fibonacci(n-2) がまた実行されることになります．よって，このままでは全く同じ計算を何回も繰り返すことになります．

これを，既に計算したものは結果を保存して使い回す，という戦略で計算してみましょう．ここでは，n=10ならば，長さ10の配列を準備して，その k 番目の要素に fibonacci(k+1) が格納されるようにします．この戦略を実装したものが，次のコードです．（ただし，必要なコードが1行足りません）

def fibonacci(n):
    if memo[n-1] != 0:
        return memo[n-1]
    a = fibonacci(n-1) + fibonacci(n-2)
    return a

n = 10

memo = [0 for i in range(n)]
memo[0] = 1
memo[1] = 1

print(fibonacci(n))