algorithm - ボトムアップ動的プログラミングは再帰的ですか?

Question

このアプローチでは、小さな部分問題が計算され、結果がキャッシュされます。次に、以前に計算された値をキャッシュしたテーブルから、小さな部分問題の既に計算された最適化された値を使用する、より大きな部分問題を計算します。では、このアプローチは再帰的ですか、それとも反復的ですか?

Answer 1

動的計画法で使用するアプローチは、実際には帰納的です。構成的帰納的証明を再帰アルゴリズムまたは反復アルゴリズムのいずれかに変えることができます。それはただの好みの問題です。たとえば、メモ化は再帰的な実装ですが、メモ化されたアルゴリズムごとに反復的なアプローチがあります。

簡単な例はフィボナッチ数です。反復的に書くことができます：

Fib (n)
{
    F_1=F_2=1;
    For i =3..n 
         F_i = F_i-1 + F_i-2;
   Return F_n;
}

再帰的に書くことができます：

  Define array F of size n;
  F [1]=F [2]=1;
  Fib (n)
  {
       If (F [n-1]==0)
            F [n-1] = Fib (n-1);

      If (F [n-2]==0)
            F [n-2] = Fib (n-2);
     F [n]= F[n-2]+F [n-1];
     Return  F[n];
  }

どちらも動的計画法であり、順序は同じです。状況によっては、再帰的に書く方が簡単です。場合によっては、反復の方が高速です。