Bottom Up動的プログラミングは再帰的ですか？

Question

このアプローチでは、より小さいサブ問題が計算され、結果がキャッシュされ、より小さなサブ問題の既に計算された最適化された値を使用するより大きなサブ問題が計算されます。だから、このアプローチは再帰的か反復的なのでしょうか？

Answer 1

ダイナミックプログラミングで使用するapprochは、実際にはinductiveです。再帰的アルゴリズムまたは反復的アルゴリズムのどちらかに建設的帰納的証明を回すことができます。それは単に味の問題です。例えば。 memoizationは再帰的な実装ですが、メモを付けたアルゴリズムごとに反復的なアプローチがあります。

単純な例はフィボナッチ数です。一つは、反復それを書くことができます。

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]; 
    } 

は、それらの両方は、動的計画法であり、彼らは同じ順序を持っています。状況によっては、再帰的に書き込む方が簡単です。繰り返しが速い場合もあります。