動的プログラミング - 最適なブレークポイント

Question

ダイナミックプログラミングを使用すると、マトリックスチェーンの乗算問題はn^3時間で解くことができますが、最適なバイナリツリー問題ではn^3時間も得られることを学びました。それをn^2に最適化する。 これはなぜですか？私は、行列の乗算の問題では、チェーンM（i、n）の最適なブレークポイントがチェーンM（i + 1、n）の最適なブレークポイントよりも大きくなる可能性があるという声明を得ました。誰かが私にこれを理解させるのを助けることができるか行列の乗算問題ではなぜこれは当てはまりますが、最適な2分木の問題ではありませんか？

おかげ

Answer 1

はI2のサブ間隔であるキーI1の間隔を考えると、I1に最適なバイナリツリーのクエリコストがI2に最適なバイナリツリーのクエリコストよりも大きくない（このかなり直観的でなければならないが、正式には、I2の最適なツリーをとり、標準アルゴリズムによってキーを繰り返し削除する）。これは、2つの半分の間の一種のバランス処理として最適なブレークポイントを見つけるプロセスを考えることができることを意味します。

行列のチェーンでは、（100,100）、（100,100）を乗算するコストは、（100,100）、（100,100）、（100,1） 2つの行列 - ベクトル乗算はよりもマトリックス行列よりも安い。