Knuth-Yao speedup

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /knuth-yao-speedup#noredirect を利用してください。
このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /knuth-yao-speedup#noredirect を利用してください。
name
Knuth-Yao speedup
short description
Knuth-Yao speedup とは、Monge な $N \times N$ 行列 $f$ に対して $\mathrm{dp}(l, r) = \min \lbrace \mathrm{dp}(l, m) + \mathrm{dp}(m + 1, r) \mid l \le m \lt r \rbrace + f(l, r)$ (ただし $l \le r$) で定まる関数 $\mathrm{dp}$ のグラフを $O(N^2)$ で求めるアルゴリズムである。