概要

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

除去

圧縮

合体

• Educational DP Contest N - Slimes
  • 最適二分探索木問題と同等
  • 素朴にメモ化再帰を考えれば解ける。

メモ

• 一般に、動的計画法による最適化では、「最適解がどうであるか」で場合分けを行う。
• 区間DP の考え方と使える状況まとめ | アルゴリズムロジック