概要

• [l, r) における何かしらの値を dp[l][r] で表す
• シチュエーションの例」
  • 最適に除去
  • 最適に圧縮
  • 最適に合体

除去

圧縮

合体

• Educational DP Contest N - Slimes
  • 最適二分探索木問題と同等
  • 素朴にメモ化再帰を考えれば解ける。
• CYKアルゴリズム
  • 文脈自由文法をCNF(チョムスキー標準形)に変換して区間DPをする
    • CNF は以下の生成規則のみからなる
      • A→BC
      • A→α | ε
      • (A,B,Cは終端記号, αは終端記号)
  • BとCが合体してAになるイメージ
  • 非終端記号を区間だと思うイメージ

文脈自由言語での区間DP

回文

回文は以下で生成できる

• S→αSα (α ∈ Σ)
• S → ε

例

• 回文にするための最小挿入回数