競技プログラミングにおける動的計画法の情報など

概要

この記事は、競技プログラミング界隈における動的計画法の情報を集めて雑多に並べたものです。自分用に集めていたものを並べただけであり、各記事の内容を保証するものでもありませんし、私も全て読んでいるわけではありません。おそらく、ここに並べている記事を探して理解しようとするよりもプログラミングコンテストチャレンジブック(蟻本)を繰り返し読んだ方が良いと思います。

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

ただ、蟻本の内容を理解したうえで、動的計画法の他の人の理解などを見るにはいいかもしれません。

解説スライド

プログラミングコンテストでの動的計画法: 一番まとまっている
動的計画法: 図がわかりやすい

解説記事

DP俯瞰? - とこはるのまとめ: DPの分類分け

normal

最強最速アルゴリズマー養成講座 動的計画法(1): chokudaiさんの記事その1
最強最速アルゴリズマー養成講座 動的計画法(2): chokudaiさんの記事その2
DPの話 - aizuzia
DPとかメモ化再帰とか - komiyamの日記
DPとかメモ化再帰とか(2) - komiyamの日記
動的計画法が苦手な人が、動的計画法が超苦手な人へアドバイスしてみる - じじいのプログラミング
Dynamic Programming – From Novice to Advanced – topcoder: 英語読めるなら是非

advanced

動的計画法 - yukicoder
Dynamic Programming Optimizations - Codeforces
Convex Hull Trick - 競技プログラミング+αなブログ

other

DPの話 - 赤い黒歴史を蓄積する

問題

蟻本に載っている例題
AOJ ALDS1 - Dynamic Programming -: 基本
AOJ DPL: 典型(途中で切れている)
Typical DP Contest - Typical DP Contest | AtCoder: 難しめだが網羅されている
yukicoder タグ: 動的計画法: レベル順に解いていくと良さそう
Codeforces Problemset tag:dp: solvedが多い順に練習するとか
TopCoder Problem Archives category: Dynamic Programming: レベルで指定して解くとか
HackerRank Algorithm Dynamic Programming
DPの練習として良さそうなやつ - kyuridenamidaのチラ裏: kyuridenamidaさんの記事

最後に

動的計画法を学ぶリソース・練習問題まとめ - フリーフォーム フリークアウト: 書いてからググったらネタが被っていた
いい記事があれば追加するので言ってくださるとありがたいです
まとめたら満足するような人間にはなりたくないとは思いつつ満足してしまった(完)