フィボナッチ数列を動的計画法で求める

f:id:hrksb5029:20210314231744p:plain
動的計画法の練習のために、簡単な問題を解きます。
動的計画法は、まだまだ使いこなせてないのですが、使って解けた時はとてもスッキリするので、好きなテクニックのうちの1つです。
色々とパターンはあるのですが、基本的には漸化式で問題を表現して、計算結果を配列に記録して、その結果を使いまわして解くようなイメージです。

最初なので動的計画法に分類しても良いのかどうかと思うくらい簡単な問題からいきます。

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_A&lang=ja

整数Nが与えられて、そのN項目のフィボナッチ数列を求める問題です。
ここでは、N=0とN=1の時は1になります。
Nの値の範囲は 0 \leq N \leq 44です。

普通に考えると、fibみたいな関数を定義して再帰的に求めることが浮かぶと思います。

def fib(n: int) -> int:
    if n == 0 or n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

ただこのやり方だと残念なことにNの値が40になってくると自分のローカルPCでは値が返ってくるのがかなり遅くなります。
再帰関数はスタック領域を消費します。
Pythonは色々とメモリが最適化されるので、予想するのが厳しいのですが、
メモリを見積もる前に計算量を考えると、fib(n-1)とfib(n-2)の2つに分岐しながら、深さは39くらいなので、 2^{39} = 549755813888で完全にアウトです。

なので動的計画法的な発想で事前に計算しようと思います。

dpという配列でインデックスをN項目とします。
dp[2]だったら、fib(2)の値が入るようにします。
まずは0を初期値としてdp[44]まで配列を作ります。
dp[0] = 1、dp[1] = 1は確定。
あとは、forループで問題で与えられたdp[N]までループでdpの値を求めます。
dp[n] = dp[n-1] + dp[n-2]

コードは以下のようになります。

N = int(input())

dp = [0 for _ in range(45)]
dp[0] = 1
dp[1] = 1

# dp[n] = db[n-1] + dp[n-2]
for i in range(2, N + 1):
    dp[i] = dp[i - 1] + dp[i - 2]

print(dp[N])

今回はとっても簡単でしたが、漸化式で表現できなかったり、どういう値をインデックスにするか迷うケースもあって、まだまだ精進が必要だと思っています。