はじめに
今回は動的計画法(DP)を実装してみようという記事になります!
動的計画法とはなんだ一体というと、こんな感じ。
対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。
かなりざっくりとした説明になりますが、そもそも動的計画法は抽象的なもので色々な種類があるようです。
ということで一番簡単?そうな箇所からみていきたいと思います。
フィボナッチ数列
動的計画法のよくある例としてフィボナッチ数列を求めるものがあります。
フィボナッチ数列とは以下のような式で表される数列のことです。
これを動的計画法を用いて実装してみます。
ボトムアップ方式
まずはボトムアップ方式といわれる方法を見ていきましょう。
public static long Fibonacci(long n) { long[] dp = new long[n + 1]; dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; }
計算は0 -> 1 -> 2 -> ... -> n
といった順番で行われ、それぞれを計算結果を記録(メモ)をしています。
計算量はです。
トップダウン方式
次にトップダウン方式といわれる方法。
public static class Fibonacci { private static long[] _dp = null; public static long Get(long n) { if (_dp == null) _dp = new long[n + 1]; // 初回のみインスタンス化 if (n <= 0) return 0; if (n <= 2) return 1; if (_dp[n] != 0) return _dp[n]; // 計算したことがある値だったら再利用 _dp[n] = Get(n - 1) + Get(n - 2); if (n == _dp.Length) _dp = null; // 使い終わったメモは削除しておく return _dp[n]; } }
これは再帰処理とメモ化を用いて値を求めます。
再帰処理は木構造によく用いられ、今回の場合も木構造と捉えることができます。
さらによく見てみるとこの再帰処理には同じ計算がなされている箇所が存在します。
ここを記録しておく(メモ化)しておくことにより計算の回数を一気に減らすことができます。
さいごに
今回は本当の触りしかやりませんでしたが、もっと色んな使い方を紹介できたらなと思っています。
またこれ動的計画法関係の記事を書くかも知れないので、良かったらそちらも見てみてください。
ではまた。