動的計画法について（トップダウン方式、メモ化、一次元）

paizaとかAtCoderとかやっていると、プログラムとして書けているはずなのに処理時間が遅くてアウト、というのが結構あって、この動的計画法について学んで、処理速度の向上を図ろうと思っているのですが、なかなかに理解しづらいので、少しずつ言語化していきます。

動的計画法の定義

• 帰納的な関係の利用
• 計算結果の記録

を満たすアルゴリズムの総称だそうです（Wikipedia）。とりあえずは適用条件等は省略します。
もう少しわかりやすくいうならば、漸化式の形で帰納的な関係を記述し、ここの計算結果について記録しておいて、その結果を参照しながら計算することによって、計算量を減らす手法ですね。

うん、全くもってわかりやすく言えてない。具体例（ベタなフィボナッチ数列）いきましょう。
フィボナッチ数列とは、a[0]=a[1]=1,a[n]=a[n-1]+a[n-2]で表される漸化式の一般解ですね。
（前二つの和によってその項の値が決まる）

普通に書いた時

fib.rb

def fib(n)
  if n <=1
    return 1
  else
    fib(n-1)+fib(n-2)
  end
end

n=gets.chomp.to_i
puts fib(n)

こんな感じ。これだと計算量はO(2^n)となり、nに代入する値が小さければ問題ないが40くらいからしんどくなる。

動的計画法（トップダウン）を用いた時

fib2.rb

@dp=[]
def fib2(n)
  if n <= 1
    return 1
  else
    if @dp[n]
      return @dp[n]
    else
      @dp[n] = fib2(n-1)+fib2(n-2)
    end
  end
end
n=gets.chomp.to_i
puts fib2(n)

@dpという配列（nがキーのハッシュのようなイメージで使う）を用意して、計算結果をこの配列に格納していきます。
計算時にはこの配列から値を参照して計算することで計算量がO(n)となり、計算量がガクッと減ります。
これならnに10000とかを代入しても一瞬です。

補足

配列を定義するときはインスタンス変数で。

最後に

なかなか理解が追いついてないのでおいおい学習しながら小出しにアウトプットしようと思います。

参考記事

https://ja.wikipedia.org/wiki/%E5%8B%95%E7%9A%84%E8%A8%88%E7%94%BB%E6%B3%95
https://www.jabba.cloud/20161020172918/