個人的に動的計画法(dynamic programming, 以下dp)はずっと苦手で, いまだに苦手なままです. そういう人はほかにも多いんじゃないかなーと思い, 自分が知ってる範囲でdpを学ぶリソースをまとめてみました. アルゴリズムの説明ではなく, 実際の問題があるものを中心にしました.

TopCoder の Dumitruによる Tutorial

Dynamic Programming – From Novice to Advanced – topcoder

なんだかんだいってやっぱりここがいいと思います. topcoderのチュートリアルの中から "Dynamic Programming: From novice to advanced" です. 練習問題も豊富に紹介されています.

ちなみに Problem Archive から問題のカテゴリを Dynamic Programming にして検索すると, dpに分類されている問題が出てきます.

TopCoder Statistics - Problem Archive

@chokudaiさんの最速アルゴリズマー

最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (1/5) - ITmedia エンタープライズ

最強最速アルゴリズマー養成講座：病みつきになる「動的計画法」、その深淵に迫る (1/4) - ITmedia エンタープライズ

おなじみ@chokudaiさんの最速アルゴリズマーから, dpを扱っている2回分です. このシリーズは, アルゴリズムの概念をわかりやすく説明してくれた上で, 読者に問題を自分で考えてといてもらうということを重視していてとてもいいなと思います.

@iwiwiさんの情報オリンピック春合宿での資料

プログラミングコンテストでの動的計画法

@iwiwiさんが情報オリンピックの春合宿で講義をした時の資料らしいのですが, とてもわかりやすい. dpを考える際のイメージや道筋がとてもわかりやすく解説されているし, あとのほうで典型的問題を紹介してくれているのが素晴らしいです.

@deqさんの ACM/ICPC国内予選突破の手引き

ACM/ICPC国内予選突破の手引き

ページ中盤に"DP特集"と名うって, 基礎的なdpの練習問題が5つ紹介されています.

pkuのdp問題一覧(中国語)

為業--艇議恵諒竃危阻

@tozangezanさんに教えてもらいました. まだやってないんですが, 結構難しい問題も含まれてるそうです.

その他

練習問題ではなくてアルゴリズムそのものの解説記事については, こちらのエントリがよくまとまっていました.

動的計画法とナップサック問題を学びたい人におすすめのサイト - ダウンロードたけし（寅年）の日記

どのように取り組むべきか

dpに限った話ではないんですが, 競技プログラミングには受験勉強っぽく取り組むのがいいんじゃないかと最近考えるようになりました. つまり,

1. 問題を解いてみる
   • あんまり深追いしても難しい場合が多いので, 時間で切るといいかも
2. 解法(他の人のコードや, あれば問題の解説記事)を見て理解する
3. もう一度解法を見ずに実装してみる

という流れです.

ただ単に問題をたくさん解くのではなくて, それぞれの問題やそれに対するアプローチをしっかりと理解・吸収して, 効率よく取り組むことができるような気がします.

この点に関しては@shiumachiさんのエントリが参考になりました.

Google Code Jam 2010 Round2 感想 - 科学と非科学の迷宮