algorithm
動的プログラミングの応用

前書き

備考

フィボナッチ数

フィボナッチ数は、従来の再帰的アプローチが多くの繰り返し計算を行うため、動的プログラミングの主題です。これらの例では、 f(0) = f(1) = 1という基本ケースを使用します。

fibonacci(4)再帰的ツリーの例を次に示します。繰り返し計算に注意してください。

非動的プログラミング O(2^n)ランタイムの複雑さ、 O(n)スタックの複雑さ

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

これは、問題を書くための最も直感的な方法です。基本的なケースn < 2達するまで、 fibonacci(n-1)を呼び出す最初の再帰的なブランチを下降させると、スタック空間はO(n)になります。

ここで見ることができるO(2^n)ランタイムの複雑さの証明： フィボナッチシーケンスの計算上の複雑さ 。注意すべき主な点は、ランタイムが指数関数的であることです。これは、後続のすべての用語に対してこのランタイムが2倍になり、 fibonacci(15)がfibonacci(14) 2倍の時間を要することを意味します。

メモ化 O(n)ランタイム複雑、 O(n)空間複雑、 O(n)複雑スタック

memo = []
memo.append(1) # f(1) = 1
memo.append(1) # f(2) = 1

def fibonacci(n):
    if len(memo) > n:
        return memo[n]

    result = fibonacci(n-1) + fibonacci(n-2)
    memo.append(result) # f(n) = f(n-1) + f(n-2)
    return result

メモ型のアプローチでは、すべての前の関数呼び出しと考えることができる配列を導入します。位置memo[n]は関数呼び出しfibonacci(n)の結果です。これは、貿易の空間複雑に私たちを可能にしないO(n)ためのO(n) 、我々はもはや重複関数呼び出しを計算する必要があるとして、ランタイム。

反復動的プログラミング O(n)実行時の複雑さ、 O(n)空間の複雑さ、再帰的スタックなし

def fibonacci(n):
    memo = [1,1] # f(0) = 1, f(1) = 1

    for i in range(2, n+1):
         memo.append(memo[i-1] + memo[i-2])

    return memo[n]

問題をコア要素に分解すると、 fibonacci(n)を計算するためにfibonacci(n-1)とfibonacci(n-2)が必要であることがわかります。また、上記のように再帰ツリーの終わりにベースケースが現れることがわかります。

この情報を使用して、ベースケースから始めて上向きに作業を開始して、ソリューションを後方に計算するのが理にかなっています。今すぐ計算するために、 fibonacci(n) 、我々は最初に、スルーまでのすべてのフィボナッチ数を計算するn 。

この主な利点は、 O(n)ランタイムを維持しながら再帰スタックを削除したことです。残念ながら、私たちはまだO(n)空間の複雑さを持っていますが、それも同様に変更することができます。

高度な反復動的プログラミング O(n)実行時の複雑さ、 O(1)空間の複雑さ、再帰的なスタックなし

def fibonacci(n):
    memo = [1,1] # f(1) = 1, f(2) = 1

    for i in range (2, n):
        memo[i%2] = memo[0] + memo[1]

    return memo[n%2]

上で述べたように、反復動的プログラミングアプローチは基本ケースから始まり、最終結果まで動作します。空間の複雑さをO(1) （定数）に近づけるために行う主要な観察は、私たちが再帰的スタックに対して行ったのと同じことです。 fibonacci(n-1)とfibonacci(n-2) fibonacci(n) 。これは、反復の任意のポイントでfibonacci(n-1)とfibonacci(n-2)の結果を保存するだけで済むことを意味します。

これらの最後の2つの結果を格納するために、私はサイズ2の配列を使用し、どのインデックスを割り当てるかは、 i % 2 0, 1, 0, 1, 0, 1, ..., i % 2 。

私は、加算が可換（ 5 + 6 = 11と6 + 5 == 11 ）であることを知っているので、配列の両方のインデックスを一緒に追加します。その結果は、2つのスポット（ i % 2示される）のうちの古いものに割り当てられます。最終結果はn%2位置に保存されます

ノート

• 時々 、それはあなたがかもしれ関数呼び出しと後続の呼び出しに答えのキャッシュを構築しますように繰り返し大きな計算を実行する機能のための反復メモ化解決策を考え出すことが最善であってもよいことに留意することが重要であるO(1)の場合すでに計算されています。