矩阵链乘法和有点不同的问题？
Matrix-chain Multiplication and a bit different problems?
我们知道矩阵链乘法问题。我的教授解决了一个密切的问题：
We want to find an order of Matrix multiplication such that number of
elements in middle matrixes (calculated in all steps of production) is
minimized (we called it cost of production). We have
A_1*A_2*A_3*...* A_n and dimension A_i is on d_{i-1} and d_i. C_{ij} =
min cost of production A_i*...*A_j sub problems and C_{ii}=0. he says
the relation for solving this problem is:
C_{ij}=min i<=k < j max{C_{ik}, C_{k+1,j}, d_{i-1}*d_j}
我听不懂，这个关系背后的想法是什么？怎么帮我？
假设我们要最小化 C(i, j)。我们可以选择什么？我们可以选择要执行的 last 乘法的位置。当它固定时，我们有两个独立的子问题（最后一次乘法之前的所有内容和最后一次乘法之后的所有内容）。所以等式 C_{ij}=min i<=k < j max{C_{ik}, C_{k+1,j}, d_{i-1}*d_j} 用简单的英语表示：
让我们选择最后一次乘法的位置并表示它是k。
让我们解决两个子问题：一个用于 (i, k)，另一个用于 (k + 1, j)。
对于固定的k，答案是这两个子问题的结果和我们在(i, j)中的所有矩阵相乘后得到的最终矩阵的大小的最大值range(即d_{i-1}*d_j，与乘法顺序无关).
我们想要最小化结果，所以我们选择所有有效值中的最小值k。
就是这样。
我们知道矩阵链乘法问题。我的教授解决了一个密切的问题：
We want to find an order of Matrix multiplication such that number of elements in middle matrixes (calculated in all steps of production) is minimized (we called it cost of production). We have A_1*A_2*A_3*...* A_n and dimension A_i is on d_{i-1} and d_i. C_{ij} = min cost of production A_i*...*A_j sub problems and C_{ii}=0. he says the relation for solving this problem is:
C_{ij}=min i<=k < j max{C_{ik}, C_{k+1,j}, d_{i-1}*d_j}
我听不懂，这个关系背后的想法是什么？怎么帮我？
假设我们要最小化 C(i, j)。我们可以选择什么？我们可以选择要执行的 last 乘法的位置。当它固定时，我们有两个独立的子问题（最后一次乘法之前的所有内容和最后一次乘法之后的所有内容）。所以等式 C_{ij}=min i<=k < j max{C_{ik}, C_{k+1,j}, d_{i-1}*d_j} 用简单的英语表示：
让我们选择最后一次乘法的位置并表示它是
k。让我们解决两个子问题：一个用于
(i, k)，另一个用于(k + 1, j)。对于固定的
k，答案是这两个子问题的结果和我们在(i, j)中的所有矩阵相乘后得到的最终矩阵的大小的最大值range(即d_{i-1}*d_j，与乘法顺序无关).我们想要最小化结果，所以我们选择所有有效值中的最小值
k。
就是这样。