Dynamic Programming - Fibonacci Number

2981 submissions, 1626 accepted solutions, 1287 scorers

フィボナッチ数列は、植物の模様など自然現象として現われたり、最も美しいとされる黄金長方形を描くなど、とても興味深い数列です。フィボナッチ数列は再帰的な式で定義することができるため、次のようなアルゴリズムで生成することができます。

fibonacci(n)
    if n == 0 || n == 1
        return 1
    return fibonacci(n - 2) + fibonacci(n - 1)

このアルゴリズムは、フィボナッチ数列の第 $n$ 項を求めることができますが、その計算量に問題があります。ここで fibonacchi() を f() と表すと、例えば、f(5) を求めるためには f(4) と f(3) を求める必要がありますが、f(4) で再び f(3) を呼び出してしまいます。


f(2) や f(3) は複数回現われますが、構造が同じで毎回同じ値を返します。このように同じ計算を繰り返すことになり、f(n) を求めるために f(0) または f(1) を f(n) 回呼び出すことになります。例えば、f(44) が 1,134,903,170 であることを考慮すると、とても大きな計算量になります。

上のアルゴリズムには一度計算した値を再び計算するという無駄があるため、次の図のように改善することができます。


これは、一度計算した f(n) の値を、配列 F[n] に記録しておくことによって、再計算を回避するという、動的計画法の基本構造に基づいており、次のようなアルゴリズムになります。

fibonacci(n)
    if n == 0 || n == 1
    return F[n] = 1 // F[n] に 1 をメモしてそれを返す
    if F[n] が計算済み
        return F[n]
    return F[n] = fibonacci(n - 2) + fibonacci(n - 1)

この考え方は、次のようにループに展開したアルゴリズムとして実装することもできます。

makeFibonacci()
    F[0] = 1
    F[1] = 1
    for i が 2 から N まで
        F[i] = F[i-2] + F[i-1]

このアルゴリズムでは、フィボナッチ数を小さい方から計算していくので、F[i] を計算するときには既に F[i-1] と F[i-2] が計算されているので、それを有効利用することができます。

このように、小さい問題の解をメモリに記憶しておいて、大きい問題の解を計算するために有効利用することが、動的計画法の基本的な考え方になります。

Reference

 

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (マイナビ)

AIZU ONLINE JUDGE のコース問題を題材にした解説書です。初級者が体系的にアルゴリズムとデータ構造の基礎を学ぶことができる入門書となっています。