昨日DPの問題を解いたとき、おかしなDPを定義してしまった。
シンプルにいえば次のような定義をした。
- dp[i] := 2iの最大値
一番おかしい点は「2iの最大値」の部分である。
2iに最大値も最小値もないのに、このような定義をしてしまった。
シンプルな例であればおかしいことにすぐ気付ける。
しかし、DPが複雑になってくると気付きにくくなる。
たとえば、昨日解いた問題ではdp
配列の次元数が10だったので、結局おかしいことに気付けなかった(まあ、実際は次元数2で十分だったんだけど)。
今後は意味のないDP定義をしないようにしよう。