区間DP
概要
区間に対する最適な値を、小さな区間から順に求めていくこと。
例
[
https://github.com/E869120/kyopro_educational_90/blob/main/editorial/019.jpg
] この絵がわかりやすい。
dp[l][r]
をlからrまでの区間(端点含む)の最適値と定義すると、
dp[l][r]
は例えば、以下のうちの良い方となる
dp[l+1][r-1]
と、
$ A_l
と
$ A_r
で定まるなにかの値
dp[l][k]
と
dp[k+1][r]
とで決まるなにかの値