競技プログラミングにおける動的計画法更新最適化まとめ（CHT, MongeDP, AlianDP, インラインDP, きたまさ法, 行列累乗） - はまやんはまやんはまやん

動的計画法更新最適化？ 参考1 参考2 参考3 セグメント木や累積和 dp[i][j] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][j] dp[i][j] = min(dp[i-1][0], dp[i-1][1], ..., dp[i-1][j]) dp[i][j] = max(dp[i-1][0], dp[i-1][1], ..., dp[i-1][j]) みたいに区間和や区間最大最小をもたせることで更新を行う。 行列累乗 DPの更新式を見てみると、一回の更新操作が行列の形になるときがある この場合は行列を繰り返し二乗法の要領でN乗しておくことで、N番目の要素を高速に取り出せる。 Convex Hull Trick 関数の形式になっている区間最小値を素早く見つける手法 参考1 参考2 わかりやすい資料 dp[i] = min{j=0...i-1}（