動的プログラミング：行列チェーンの乗算

Question

私は動的プログラミングに関するCormenによるアルゴリズムの紹介を読んでいます。ここで

いくつかのバックグラウンドに

を与えるテキストスニペット行列鎖乗算展示の問題は 下部には最適です。 AkとAk + 1の間の積を分割するA1 A2 ... Anの最適なカッコでは、A1 A2 ... A kとAk + 1 Ak + 2のカッコの問題に対する最適解が含まれていることがわかりました。 。 。 An。

行列連鎖乗算の本には、theta（n square）のサブ問題があります。

私の質問は、著者がどのようにn個の正方形の問題が出てきたかです。 どのようなplsが例を挙げてくれますか？

ありがとうございます！

Answer 1

各サブ問題は、行列の連続サブシーケンスAi, Ai+1, ..., Aj-1, Ajの問題を解決することを含む。このサブシーケンスは、2つのインデックスiとjによって特徴付けられます。それぞれにnの可能な選択肢があるので、部分問題の数はtheta（n ）です。正確な数値はi <= jという制約のためn(n+1)/2です。