Matrix Chain Multiplication Dynamic Equation I am thinking about the derivation of the following dynamic equation: $$F(n_1,...,n_{k+1};k)=\min_{1<i<k+1}\{n_{i-1}n_i n_{i+1}+F(n_1,...,n_{i-1},n_{i+1},...,n_{k+1};k-1)\}, k=1,...,h$$
Let me explain you the details. We have a matrix $M_k$ of dimension $n_k\times n_{k+1}, k\in\{1,...,h\}$. I want to compute $M_1... M_h$. $F(n_1,...,n_{k+1};k)$ is the minimum number of multiplications which we need to get $M_1... M_h$. Now I want to check if the above equation is the correct dynamic programming equation.
I am not sure how to derive the above form. I think it has something to do with cutting the matrix multiplication, i.e I cut $M_1... M_h$ to two matrices of order $n_{i-1}\times n_i$ and $n_i\times n_{i+1}$. So now we need to optimize the subtrees (we we illustrate the whole multiplication as a tree) but I do not see the rest.
 A: This is the task of putting brackets in matrix multiplication such that it'll minimize operations count. There's some ambiguity in notation and I'll replace $F(n_1, \dots, n_{k+1}; k)$ with $F(n_1, \dots, n_{k+1})$.
Suppose that we have to put first inner-most brackets.
At first step you have to choose a pair of matrices to be multiplicated. If you choose matrices $M_i$ and $M_{i+1}$ and multiply them, that will cost you $n_{i}\cdot n_{i+1}\cdot n_{i+2}$ multiplications. After that you obtain the operation minimizing task for set of matrices 
$M_1, \dots, M_{i-1}, (M_i \cdot M_{i+1}), M_{i+2}, \dots, M_h$ which costs exactly $$F(n_1,...,n_{i-1},n_i, n_{i+2},...,n_{h+1}).$$ $F(n_1,...,n_{h+1})$ is obtained exactly as a minimum among all inner-most variants of brackets: $F(n_1,...,n_{h+1})=\min \limits_{1<i<h+1}\{n_{i}\cdot n_{i+1}\cdot n_{i+2}+F(n_1,...,n_{i-1},n_{i},n_{i+2},...,n_{h+1})\}$.
Also, you could do that another way. You may choose the outer-most bracket first and it will result in such dynamical equation:
$$F(n_1,...,n_{h+1})=\min_{1<i<h+1}\{n_{1}n_{i+1} n_{h+1}
+ F(n_1, \dots, n_{i+1}) + F(n_{i+1},\dots, n_{h+1})\}.$$ 
This corresponds to splitting the product in two brackets $(M_1\cdot\dots\cdot M_i)$ and $(M_{i+1},\dots, M_{h+1})$. To multiplicate them we have to spend $n_1 n_{i+1} n_{h+1}$ iterations. But to multiplicate matrices inside these two brackets we have to spend $F(n_1, \dots, n_{i+1})$ and $F(n_{i+1},\dots, n_{h+1})$ operations respectively. And, again, we take minimum among all variants of outer-most brackets.
