動的計画法

アルゴリズムの分類の一つ。頻出する言葉ではあるが明確な定義はなく、見た目の大きく異なるいくつかのアルゴリズムがこの概念に含まれるとても抽象度の高い概念である。

Educational DP Contest 動的計画法の三通りの実装 Jを解いたあたりで「このDPは何を定義域とし、何を値とするのか」を明確化するのが良い気がした

• DPの問題を10問くらい解いていて思ったんだけど、DPの問題の解法は「何を定義域として、何の値をDPするのか」を明確にした方がいいんじゃないかな。区間DPは区間を定義域にしてて、確率DPは確率を値にしてて、bit DPは部分集合を定義域とするDPの単なる実装テクニック、ゴチャゴチャすぎる

• そして実装時に「定義域が大きすぎるので値域と交換する」というテクニックが使われることがある DP_E

• https://qiita.com/drken/items/dc53c683d6de8aeacf5a

• https://qiita.com/drken/items/a5e6fe22863b7992efdb

• https://www.slideshare.net/hcpc_hokudai/advanced-dp-2016

• https://dalekspritner.hatenablog.com/entry/2018/09/27/231030

• https://atcoder.jp/contests/dp

• https://atcoder.jp/contests/tdpc

• https://juppy.hatenablog.com/entry/2019/03/19/Educational_DP_Contest(EDPC)_M~P_Python_競技プログラミング_Atcoder

• https://kyopro-friends.hatenablog.com/entry/2019/01/12/230754

• https://qiita.com/Series_205/items/7d2c57b45179006d0bc6