サンリオピューロランド

競技プログラミングをします。

競技プログラミングにおけるDPの考え方

はじめに

この記事はAtCoderの灰色から青色程度を対象にしています。DPの紹介と、実際の問題へのアプローチの仕方を具体的に書いていきます。そのため解説にネタバレを含むことがあるため注意してください。

改善案や修正点、感想などは@Cinnamon_VRまで

DPとは?

DP(動的計画法)とはアルゴリズム設計手法の1つで、状態空間が広すぎて全探索できない場合に状態をまとめることで状態空間を小さくするテクニックです。DPは水色程度の実力があっても苦手な人が多く、その原因は状態空間をどのようにまとめればよいか、遷移をどのように定義すればよいかがわかりにくい点だと考えています。一般に次の点に注目すると状態が定義しやすいでしょう。

・同じ状態に含まれるものは問題制約で同一視できる
たとえばナップザックDPでは「重さ」が同じであるような買い方を同一視しています。

・同じ状態にあるものの中で問題制約を満たすものと満たさないものが混在していない
DPは状態を圧縮しますが、必要な情報まで圧縮してはいけません。


では、上記の点に注意しながらそれぞれのDPの特徴を見ていきましょう。

お品書き

・はじめてのDP (灰~緑)
1次元DP 
多次元DP

・工夫が必要なDP(緑~水)
bitDP

・さまざまなDP(水~青?)
行列累乗
桁DPのような複数のDPテーブルをもつ考え方
区間DP
挿入DP
文字列DP
ゲームDP
木DP

(工事中...)