動的計画法の擬似言語

科目B応用問題で出題される動的計画法 (DP)。フィボナッチ・最大部分和・ナップサックを擬似言語で読みこなします。

日野 こむぎ

動的計画法って、再帰と何が違うの?

藤森 さやか 先生

動的計画法?
(DP) は「部分問題の解を表に記録して再利用する」手法よ。
再帰の弱点 (同じ計算の繰り返し) を解消するの。

青木 澪

フィボナッチ数列の例で見てみましょう。
素朴な再帰は O(2ⁿ) で激遅、DP なら O(n) で高速になるの。
メモ化?
とも呼ばれるわ。

/* DPでフィボナッチ数列 (ボトムアップ式) */
○ 手続: fibDP(整数型: n)
  整数型の配列: dp
  整数型: i
  if (n ≦ 1) return n
  dp[1] ← 0
  dp[2] ← 1
  for (i を 3 から n+1 まで 1 ずつ増やす)
    dp[i] ← dp[i-1] + dp[i-2]
  endfor
  return dp[n+1]

桃井 すみれ

再帰よりも、ずっと速そうですぅ

青木 澪

そうなの。
各 dp[i] は1度しか計算されないから、fibDP(50) でも一瞬で終わるわ。

藤森 さやか 先生

もう一つ典型例を見てみましょう。
連続部分配列の最大和を求める、カダネのアルゴリズムね。

/* カダネのアルゴリズム: 連続部分和の最大値 */
○ 手続: maxSubArray(整数型の配列: a)
  整数型: i, currentSum, maxSum
  currentSum ← a[1]
  maxSum ← a[1]
  for (i を 2 から aの要素数 まで 1 ずつ増やす)
    if (currentSum + a[i] > a[i])
      currentSum ← currentSum + a[i]
    else
      currentSum ← a[i]    /* リセット */
    endif
    if (currentSum > maxSum)
      maxSum ← currentSum
    endif
  endfor
  return maxSum

青木 澪

「直前までの和に今の値を加えた方が、今の値単独より大きいか?」を判定して、累積を続けるか単独でリセットするかを決めるの。
これで O(n) で解けるわ。

日野 こむぎ

DPって、表で管理しながら計算していくイメージなんだね!
あたしも実装してみたい!

藤森 さやか 先生

DPは「部分問題の最適解 → 全体の最適解」というアプローチなのよ。
試験では、DP表の遷移を埋める穴埋め形式が定番ね。