Essence of 動的計画法

( ´・ω・`) つ [jawp:動的計画法]

概要: 再帰は読みやすいけど、スタック・オーバーフローしやすいし、時間オーダーも読みにくい。それってせっかく計算式がわかっててもTLEするかもしれないってことでしょ？ 末尾再帰化 (a.k.a tailrec)もいいけど言語によりけりだし。なので、値を列挙してみよう！ｗ

目標

• 記事の中で具体例を示す
• 動的計画法なアルゴリズムをかけるようになること

適用要件

• 本来の問題がより簡単な部分的な小問題の集合に還元可能であること
• 重複するパラメーターの小問題があること
  • そうでないと適用する意味がない
  • かつ、関数自体がパラメーターが同じなら必ず同一の動作をすること
• 各々の小問題が互いの解に依存していないこと (f(p)がf(q)に依存していて、f(q)がf(p)に依存したような問題では適用できない)
• ナイーブなアルゴリズムよりオーダーが小さいこと (ナイーブなアルゴリズムが$O(log\ N)$ならそっちを使ったほうがいい)

レシピ

• 関数
  • ベースケースの値が必要になるパターンがある
• 本来の問題を構成する小問題の解を覚えておくなにか (たいてい、数字の多次元配列やジャグ配列として実装されることが多い)
• 小問題の解のマージの仕方 (最適化問題なら最もコストが低かったり、利益が高かったりする選び方)

例

例1: フィボナッチ数列

再帰として実装すると以下のようになる (ここで、このコードのオーダーは$O(\phi^N)$ - つまり指数時間)

fun fib(n: Int): Int {
  if (n == 0) return 0
  if (n == 1) return 1
  return fib(n-1) + fib(n-2)
}

シンプルだが、これは時間がかかりすぎる。$N$が指数に来ているので、あっという間に爆発してしまう。TLEでお亡くなりになってしまうので、タイトルに含まれるように動的計画法を用いて書き直してみたい。 しかしその前に、適用要件とレシピを確認してみたいと思う。

適用要件

• 本来の問題が部分的な小問題の集合に還元可能であること: これはfib(n)はfib(n-1)とfib(n-2)という小問題の解に依存し、fib(0)とfib(1)は定数であることから、任意のfib(n)について成り立つ。
• 重複するパラメーターの小問題があること: 例としてfib(3)を取り上げると、fib(2)とfib(1)を呼び、fib(2)はfib(1)とfib(0)を呼ぶ。ここで、fib(1)が2回呼ばれているのでこの要件を満たす。
• 関数自体がパラメーターが同じなら必ず同一の動作をするか: ここで一切副作用や乱択要素をもちいていないので、満たされている。

レシピ

• 関数: fib(n: Int): Int
  • ベースケースの値はn=0 -> 0, n=1 -> 1
• 本来の問題を構成する小問題の解を覚えておくなにか: 今回はnから求められる値を格納しておければ良いので、Array<Int>
• 小問題の解のマージの仕方: 合計

では実装してみよう。

val MAX = 30000
// ここで、まだ格納されていないことを示すのに-1を用いた
val dp = IntArray(MAX) { _ -> -1 }

// O(n)
fun init() {
  dp[0] = 0
  dp[1] = 1
  for (i in 2..MAX) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
}

// O(1)
fun fib(n: Int): Int {
  return dp[n]
}

指数時間より遥かに良くなった。線形時間なんて可愛いもんだ。