Monge性
https://gyazo.com/f4f6e20c907ce5ab25f8c245cabcc68d
「もんげ」ではなく、「もんじゅ」と読むそう。高速増殖炉かな？
Monge性を満たすDPなら、$ O(N^3)を$ O(N^2)にしたりできるらしいです。知らんけど。
参考
Knuth OptimizationとかKnuth-Yao speedup、最適二分探索木問題とも言うらしい
二変数関数があって、その関数が
$ i <= j
$ k <= l
$ f(i,l) + f(j,k) >= f(i,k)
を満たすとき、その二変数関数はMonge性を持つといいます。うーんわからん。
二変数関数とは？
$ f(x,y)みたいなやつのことです。2つの値を渡せば、値が一つに決まるみたいな。
そう思ったらdp[i][j]も2つの値を渡せば(iとj)値が決まるので二変数関数なのでは？と思ってしまった
「理屈とか証明とか理解しようと思ったら多分凄い時間かかるから考え方だけ教えなさ〜い！」