動的計画法（DP）を勉強したときの方法をまとめておきます。
蟻本を読んでコードを書いた
蟻本には、単純な再帰（もちろんTLE） → メモ化再帰（これでもAC） → DPに発展的に書き換えていく手順が載っていますので、これを読んで理解し、自分の理解だけをもとにコードを書いて書き換えていってみました。
この時点ではDPをメモ化再帰からの書き換えなしにいきなり書けるようになる気はしませんでした。しかし、漸化式で書ける問題はDPで解けるんだなということはわかりました。つまり、文字列だか数列だかが与えられたとき、どちらかの端から順番に処理していって、今処理している桁より前の桁の結果だけをもとに今の桁の結果が求まるなら、DPで書けるということです。
ABC135 D問題がDPで解けた
ちょっと考えて「端から順番に処理して、今処理している桁より前の桁の結果だけをもとに今の桁の結果が求まる」ということは分かりましたが、DPをいきなり書ける気がしなかったので、メモ化再帰を書くことにしました。
ところが、この時点でsys.setrecursionlimitを知らなかったのでメモ化再帰が再帰深さ上限オーバーでREしてしまいました。仕方なく唸りながらDPに書き換え、ACすることに成功しました。リアルタイムにコンテスト参加していたからこそ自力でここまで考えられたと思います。
これでちょっと自信がつきました。
ABC129 C問題がDPだということを知って解いてみた
この問題はDPを勉強し始める前に、壊れている段で区切ってその間の組み合わせを求める力技で解いていました。しかしこの記事でDPで解けるということを知り、解法は読まずに自力でDPを書いてみることにしました。
壊れている段は0、壊れていない段はdp[i-2] + dp[i-1]というだけの単純なdpなので、慣れないいきなり書きで時間はかかりましたがACできました。
Educational DP Contestを解いてみた
優しい人がEducational DP Contestというものを作ってくれていたので、Aから順番に解きました。Eのようなイレギュラーなもの（蟻本に解説があります）は初見では解けませんでしたが、他の問題は意外にもいきなり書けるようになっていました。
最短実行時間の人のコードを読むと、dpの範囲を絞ったり、空間計算量が小さかったりと、恐ろしくエレガントな解答があってかなり勉強になりました。
未完
まだ長いDP坂を登り始めたばかりです。よい課題などあればぜひ教えてください。