動的計画法
値
DPテーブルの値は、問題によってあまり大きく変わることはない
最適化問題の場合は部分問題の最適値
数え上げの場合は条件を満たす対象の個数
状態
- 現在注目している位置
- 区間
- 部分問題の最大値
- 列の中の位置
- 部分集合
- 何かの最大・最小値
- 何かを割ったあまり
遷移
dpの遷移の実装には、大きく分けて貰うDPと配るDPがある。 貰うDPは、部分問題の答えを統合する計算式を明示的に書いた形である。 配るDPは、解を構成していく過程を明示した形である。
桁DP
ある自然数以下の数を探索する
上位i桁を見てすでにRより小さくなっているなら、その後はどんな数を連結してもRより小さいまま →すでにRより小さいかどうかを表すlessフラグを用いる
複数のlessフラグを用いる
繰り上がりを考慮する
下の桁から繰り上がってきたかどうかを表すcarryフラグを用いる
繰り下がりについても、下位の桁のために1だけ残しておけばいいので、同様にcarryフラグを用いれば良い