概要

5次元だろうが、素直なDPならば結構思いつくようになったし、バグって無限時間溶かすことがなくなってきました。僕は青コーダーなんで、ほんまあまり役に立たない記事ですが、ある種の「アルゴリズム設計者の発達過程」として見てもらえれば良いです。

できるようになったこと

あまりDPをバグらせない。バグっても直せる。
そもそも「こんなんDPじゃなきゃ無理ｗ」という感覚がついた（これは結構前に）。凸凹感覚というか、全探索しないといけなそうだけど2ⁿとかn!とかで、他に解放が思いつかない場合など。隣と関係なさそう感（一番近い回文数列みたいなやつはきついよなあ）みたいなのもわかる

少し考察を眺めに取るようにした。厳密に考えるようになった。紙にきちんと数式に書くようになった。（これはDPの状態と遷移をコードに明示することともつながっていそう）
デバッグ時、自分の目で経路復元をするようになった（つまり経路復元ができるようになることは普通のDPのデバッグに必須。どこから来た値なのかを探す必要がしばしばあるので）
バグっていようがいまいが、とりまデバッグ出力を書くようになった（必ずバグってるので）。有効な状態（INFとか0とか自明じゃないもの）について、I << j <<< “ : “ << val << “ “ << hoge << “ “ << hugaみたいなデバッグ出力ををするようになった。遷移後の値を出力するようにした。
コメントに必ず状態と遷移を書くようにした
配っているのか集めているのかは必ずコメントで明記するようにした。
何でも一般化してみるようになった。長さnのpermutationの中で、転倒数がkのものは？とか言われたら、長さiのpermutationのなかで、転倒数がjのものは？と言い換えてみる