列・編集距離・区間合成DP

概要

配列上のDPは、添字が似ていても依存関係で分ける。列DPは処理済みprefixへ一要素を追加し、prefix分割は最後のブロックを固定する。区間合成は独立な小区間の答えを合わせ、区間拡張は訪問済み区間の外へ一歩進む。

LISは列DPのうち、末尾の支配関係で状態を圧縮する流れとして独立に読む。問題名や配列という入力形式ではなく、「何を固定すると残りが同じ問題になるか」で節を選ぶ。

状態設計を土台に、列の選択、二列の編集距離整列、LISの支配関係、prefix分割、独立な区間の合成、訪問済み区間の拡張を別の依存構造として比較する。

考え方

列を左から伸ばすDP、prefixを最後のblockで分けるDP、小区間を合成するDP、訪問区間を拡張するDPは別の依存構造を持つ。何を最後に固定すると残りが同じ問題になるかで選ぶ。

成立条件と計算量

列は典型的にN段、区間はO(N²)状態、全分割点を試す区間合成はO(N³)となる。状態が似た添字でも初期値と処理順を借用しない。子単元で依存の向きと必要な追加情報を確かめる。

下位単元

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

導入対象の目安: 緑色(800–1199)。prefix・最後の要素・区間という状態の違いを見渡す入口。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 動的計画法。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-dp-sequence-interval

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

このUnitでは扱わないもの

  • bitmask集合や容量だけを状態にし、列順・区間分割を持たないDP。

根拠