動的計画法を利用したプログラミング #C++

動的計画法を少し勉強したのでメモ

動的計画法とは ...

結構ざっくりですが…
動的計画法(Dynamic Programming)というアルゴリズムは部分問題の結果を記録しながら解いていくアルゴリズムでDPとか言われます。
(Wikipediaはこちら)

以前に計算したことがあるやつはその値を利用して無駄な計算を省こうぜ、みたいな理解をしています。

例

フィボナッチ数列を例題でよく見るので実際に実装してみてみます。
ちなみにフィボナッチ数列は

f(0) = 0
f(1) = 1
f(2) = f(1) + f(0)
...
f(n) = f(n-1) + f(n-2)

みたいな数列です。
まず再帰を使った方法です。

fib.cpp

#include <iostream>
int fib(unsigned int n){
  if (n == 0) return 0;
  if (n == 1) return 1;
  return fib(n - 1) + fib(n - 2);
}
int main(){
  int n;
  std::cin >> n;
  std::cout << fib(n) << std::endl;
  return 0;
}

こんな感じでかけると思うのですが n が多いと(書くのが)大変なのでn = 5を考えると

  fib(5) 
= fib(4) + fib(3) 
= (fib(3) + fib(2)) + (fib(2) + fib(1)) 
= ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1)) 
= (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

n = 5でも以前やったことがあって結果がわかっているような計算を何度かしています。
それが n = 10とか100とかになると思うと…

ということでDP！
mainとかは同じなので省略します。

dp.cpp

int fib(int n){
  int memo[n+1];
  memo[0] = 0,memo[1] = 1;
  for(int i = 2;i <= n;i++){
    memo[i] = memo[i-1] + memo[i-2];
  }
  return memo[n];
}

↓みたいな感じで計算していきます。

memo(0) = 0
memo(1) = 1
memo(2) = 1 (= memo(1) + memo(0))
memo(3) = 2 (= memo(2) + memo(1))
memo(4) = 3 (= memo(3) + memo(2))
memo(5) = 5 (= memo(4) + memo(3))

以前に計算した値を利用してやっているので随分無駄がなくなった感じがしますね。

あとメモ化とかいうのもあります。
これも計算結果をメモして再利用する方法です。

memo.cpp

#define N 10000

int memo[N];
bool isOK[N];

int fib(int n){
  if(isOK[n]) {
    return memo[n];
  } else {
    isOK[n] = true;
    return memo[n] = fib(n-1) + fib(n-2);
  }
}

int main(){

  // 入力とか

  memo[0] = 0,memo[1] = 1;
  isOK[0] = isOK[1] = true;
  cout << fib(n) << endl;
  return 0;
}

計算済みかどうかをisOKというbool型の配列で記憶して計算済みならその数値を、
まだなら計算結果をmemoに、isOKをtrueにします。

実行速度はだいぶ変わってくるので覚えておくといいことがあるかもしれません。
*上記のプログラムはint型で記述しましたが、値によってはオーバーフローするのでlong longを使用したり、また欲しい型に適宜変更して利用してください。

今後は探索アルゴリズムとかも勉強したい。