TopCoderのDPの問題を解いていて、色々思うことがあるので書いていく。
DPの種類
数え上げDP
配るDPが多い。初期値は dp[0][0]...[0] = 1みたいなのが多く、この1を様々な状態に分配していく。根から葉への有向辺をもつ木をイメージするとわかりやすい。
遷移に順列や組み合わせが出てくることがある。この場合は数学の知識が必要になる。実際に問題を解くときに写像12相を使えるかどうかがカギ。これはプログラミング力というよりは数学力
確率DP
数え上げDPと同じく配るDPが多い。そして初期値もdp[0][0]...[0] = 1みたいなのが多い。しかしこの1は数え上げDPのときと意味が異なる。これは割合を表す。よって分母を求める必要があり、数え上げDPよりも一段階複雑度が増す。
期待値DP
数え上げDPや確率DPと異なり、貰うDPが多い。dp[0][0]...[0]は初期値ではなく求めたいものになることがある。期待値を求めるときに確率が必要になるので、確率DPよりも更に一段階複雑度が増す。
DPの問題を解く際にこれから意識すること
- 配るDPか貰うDPかで悩んだときは、考えやすいほうを選ぶ
- DPの状態を定義することがゴールではない
- 遷移には様々なパターンがある。複数の状態を参照することもあるし、複数の状態に遷移することもある。ひとつのパターンに固執しないこと
あと、順列と組み合わせの勉強をする。絶対競プロで役に立つ。
