上图中的数字表示子矩阵链的长度，根为4，即初始矩阵链；它可以分为1+3,2+2,3+1三种情况，这三种情况又可以各自细分。

这里暴露了一个问题，请看图中的两个涂色的子树。两个子树的节点数字是一样的。但是左边这个子树的根节点3代表的是A₂A₃A₄这个乘积；而右边这个代表的是A₁A₂A₃这个乘积。由于A₁,A₂,A₃,A₄四个矩阵的秩是未知的，它们很可能不相同，则A₁A₂A₃和A₂A₃A₄的最优解也很有可能不同。换言之，它们并不是同一个子问题，它们的子子树也并不相同。

这个问题意味着我们对子问题的定义不够严谨——子问题不能只用长度这个变量来确定。也就是说，如果在bottom-up的dp中用一个数组记录子问题的值，那么这个数组应该是一个二维数组。子问题不仅应该由子矩阵链的长度确定，还要加上起始index这样的信息。

为了更通用一些，我们不用起始index+长度，而选用起始index+结束index的定义方法，这是二维dp的惯用套路，在许多字符串和数组有关的问题中都有用到。

设用一个二位矩阵dp[][]存取子问题的解。定义dp[i][j](1<=i<=j<=n)的值为A_i...A_j的最小乘法次数。则按照以上的思路，可以把A_i...A_j再递归细分为子问题A_i...A_k和A_k+1...A_j(i<=k<j)，则A_i...A_j的最优解值为两个子问题最优解的和+两个子矩阵链相乘的乘法次数。即有

i==j时，dp[i][j] = 0;

i <j时，dp[i][j] = min{dp[i][k] + dp[k+1][j] + p_i-1p_kp_j}, k = i...j-1 (p为各个矩阵的秩，见题目一节)

到此为止，最关键的一步顺利完成啦（楼主写得好累，击掌╭(○｀∀´○)╯╰(○'◡'○)╮）。在这一步中，我们递归地定义了子问题最优解的值，完成了算法最核心的设计部分。在后面两步中，我们只要把上面这两个式子翻译成代码，再注意一些实现细节就可以了。