競技プログラミング初心者の方が動的計画法(DP)を勉強するのにお勧めの問題があります。AtCoderで開かれた「Typical DP Contest(tdpc)」です。2013年8月と結構昔に開催されたのですが、今でもたくさんの方が解いています。

このコンテストは、そもそもが「動的計画法の練習をすることを目的」として開催されて、「出題される問題はすべて(他のコンテストで使用できないほど)典型的なDPの問題です」とあるように、ちゃんと理解してみるとDPに関する典型的なテクニックをたくさん学べるとてもいいコンテストだと思います。ただ、難易度は高くて(TopCoder SRM d2 hard程度のものが多いとのこと)、初心者にとってはハードルが高いです。作者の方が一言ヒントをつぶやかれたり、いろいろな方がブログで解説を書かれていますが、一回読むだけではなかなか理解するのが難しいものが多いです。

そこで、競技プログラミング初心者の人にもわかりやすい解説を目指してこのブログを作成しました。もしわかりにくいところなどがあれば指摘していただけるとありがたいです。

また、自分にとってわかりやすかったと思われる他の方のブログも紹介させていただきます。あくまでも私にとってわかりやすかった記事ですので、そのほかにもいろいろ検索して勉強することをお勧めします。

問題概要解説ブログ
A コンテスト基本的な2次元のDPGrenache
B ゲームゲームの最善手Grenache
kagamizさん
C トーナメント確率Grenache
simeji_tanさん
D サイコロ確率、4次元のDP、素因数分解Grenache
kmjpさん
E 数組合せの数、桁DPGrenache
kmjpさん
tshitaさん
F 準急組合せの数、累積和Grenache
mayokoさん
G 辞書順組合せの数、文字列の部分列Grenache
simeji_tanさん
osakさん
H ナップザックナップサック問題の変形、最大値Grenache
kagamizさん
kmjpさん
I イウィ最大値、文字列Grenache
osakさん
???
J ボール期待値、bitDPGrenache
kagamizさん
K ターゲット最大値、LIS、幾何Grenache
kmjpさん
L 猫和の最大値、累積和Grenache
simeji_tanさん
kmjpさん
M 家組合せの数、巡回セールスマン問題(TSP)、
bitDP、行列累乗
Grenache
simeji_tanさん
N 木組合せの数、逆元、パスカルの三角形Grenache
kmjpさん
simeji_tanさん
O 文字列組合せの数Grenache
simeji_tanさん
hadroriさん
P うなぎ組合せの数、木構造Grenache
osakさん
shifthさん
Q 連結組合せの数、文字列、配るDPGrenache
osakさん
shifthさん
R グラフ
S マス目
T フィボナッチ

まだすべての問題を解けていないのですが、解けたらブログに書きたいと思います。