動態規劃：矩陣鏈乘法

Question

我正在閱讀Cormen等關於動態規劃的算法介紹。

這裏是文本段，其給出了一些回地面

矩陣鏈乘法展品的問題的最優 子結構。我們觀察到，在A2和A + 1之間分割產品的A1 A2 ... An的最佳括號內包含了對A1 A2 ... A k和A k + 1 A k + 2的括號問題的最優解。 。 。一個。

在矩陣鏈乘法的書中有θ（n平方）的子問題。

我的問題是作者如何提出有n個方形子問題？ 任何人都可以舉例說明我們是如何與這個一起來的？

謝謝！

Answer 1

每個子問題都涉及解決矩陣連續子序列Ai, Ai+1, ..., Aj-1, Aj的問題。這個子序列的特徵是兩個指數i和j。由於每個可能的選擇有n，子問題的數量是theta（n ）。由於約束i <= j，確切的數字是n(n+1)/2。