思路：运用动态规划去解决问题，这个时候子问题并不是属于父问题的"前缀"，也不是属于父问题的"后缀",而是属于父问题的某个区间之内。

示例

矩阵线程

给一个矩阵序列 ABCD，它相乘的方式可以表示为 (ABC)D=AB(CD)=A(BCD)=... ，不同的添加括号方式会导致不同的计算次数，比如

A: 10 × 30 matrix
B : 30 × 5 matrix
C : 5 × 60 matrix
复制代码

那么

 (AB)C = (10×30×5) + (10×5×60) 
       = 1500 + 3000 
       = 4500 操作
 A(BC) = (30×5×60) + (10×30×60) 
       = 9000 + 18000 
       = 27000 操作
复制代码

针对这种现象，如何添加括号才能使得操作次数最少呢？
在输入中，矩阵用一个数组表示，比如输入 40 20 30 10 30 表示矩阵A有40行，20列，矩阵B有个20行，30列，矩阵C有30行10列，矩阵D有10行30列
输入规则为

2   //表示总共有两个输入
5  //下一个要输入的数组大小
1 2 3 4 5  //数组的值
3 3 3
复制代码

分析如下：
假设有如下形式的矩阵做乘法

如果直接按照顺序来计算,先乘A.B，得到的结果再乘C

如果优先运算 B.C ，结果再乘A

可以看到第二种方式消耗的时间会更少。扩展到假设有n个矩阵相乘，无论是怎么添加括号，改变执行顺序，最后一定是其它的都计算完毕，只需要计算剩余的两个矩阵相乘。假设区分最后两部分的下标是k,那么最后一次执行为

要达到最后一步，则需要把两个部分的结果分别计算出来，假设先计算（ $A_i,...,A_{k-1}$ ），类推上面的经验，必定存在一个节点i来划分得到

可以看到要得到最终问题的解，这样一层层倒推下来，需要解决类似 $（A_i,...,A_{k-1}）$ 这样的，属于原始问题的某个区间内子集的问题。

以数据长度为4举例，即3个矩阵ABC相乘,希望得到最少的计算次数。