常用算法思想之动态规划的区间子集思想
思路：运用动态规划去解决问题，这个时候子问题并不是属于父问题的"前缀"，也不是属于父问题的"后缀",而是属于父问题的某个区间之内。
示例
矩阵线程
给一个矩阵序列 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,那么最后一次执行为
要达到最后一步，则需要把两个部分的结果分别计算出来，假设先计算（
），类推上面的经验，必定存在一个节点i来划分得到
可以看到要得到最终问题的解，这样一层层倒推下来，需要解决类似
这样的，属于原始问题的某个区间内子集的问题。
以数据长度为4举例，即3个矩阵ABC相乘,希望得到最少的计算次数。 最终要计算的结果用dp(0,3)，其中0表示输入的矩阵数组中的下标为0的位置，3是下标为3的位置，以此表示最终要囊括ABC三个矩阵。 按照上述分析，要计算dp(0,3)，它的最后一步有一下两种划分方式
- dp(0,1)与dp(1,3),即计算规则为A(BC)
- dp(0,2)与dp(2,3),即计算规则为(AB)C
比较二者那种方式计算最少即可得到最终结果 要得到dp(1,3)则需要知晓dp(1,2)与dp(2,3)的需要最少的次数
当然这里只需要直接相乘即可
同理计算dp(0,2)
整个过程用图表示如下:
目标为计算图中的问号dp(0,3)，表格中的横轴表示开始计算的下标，纵轴表示结束计算的下标，这种表示方式，当横轴值大于纵轴值时(如坐标2,0)，可以忽略，不需要计算。根据最后的划分结果，要得到dp(0,3)先的计算A方案：dp(0,1)与dp(1,3) 或者是 B方案：dp(0,2)与dp(2,3)
A方案的计算用 x 表示计算过，B方案的计算用 o 表示计算过
dp(0,1)和dp(2,3)分表表示一个矩阵，不涉及操作，也就是作为初始值为0 dp(0,2)和dp(1,3)可以分别再划分为
- dp(0,2):dp(0,1)与dp(1,2),其中dp(0,1)的结果可以复用dp(0,1)
- dp(1,3):dp(1,2)与dp(2,3)，其中dp(2,3)的结果可以复用dp(2,3)
特意只说明dp(0,1)和dp(2,3)的复用，是为了表明结果的可复用性，不需要重复计算
再次回顾上述过程
- 目标要得到dp(0,3)
- 需要先计算dp(0,1) dp(1,3) dp(0,2) dp(2,3)
- 为得到2的结果，需要先获取dp(0,1) dp(1,2) dp(2,3)的结果
- 为得到3，从下标之间的关系可以看出，他们就是初始值，即只要有初始化的过程即可
现在逆向来看(从4到1)，计算的过程可以抽象为如下的一个过程
先按照蓝线箭头部分计算对应位置的值，将它存储起来，然后计算绿线部分的值，它会复用蓝线部分的结果，最终得到目标dp(0,3)。
class GFG {
public static void main (String[] args) throws IOException{
//处理数据的输入
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int round=Integer.parseInt(br.readLine());
GFG fgf=new GFG();
for(int i=1;i<=round;i++){
int dataNum=Integer.parseInt(br.readLine());
if(dataNum<=2){
//少于1个矩阵没有必要计算
System.out.println(0);
//记得要读掉这部分数据，不然顺序就乱了
br.readLine();
continue;
}
int[] arr=new int[dataNum];
int count=0;
for(String dataStr:br.readLine().split(" ")){
arr[count++]=Integer.parseInt(dataStr);
}
int[][] dp=new int[dataNum][dataNum];
for(int L=2;L<dataNum;L++){
//L表示，从start开始后面还有几个字符,L用来标识从表格左下角到右上角的一个过程
for(int start=0;start<dataNum;start++){
//start 表示开始计算的地方,start表示从表格左上角到右下角的一个过程
int end=start+L;
if(end>=dataNum){
//不能超过数组的长度
end=dataNum-1;
}
if(end-start<=1){
//赋予初始值
dp[start][end]=0;
continue;
}
int min=Integer.MAX_VALUE;
//比较当前所有可能的取值，并获取最小的值作为子问题的最优解
for(int k=start+1;k<end;k++){
int tempMin=dp[start][k]+dp[k][end]+arr[start]*arr[k]*arr[end];
if(tempMin<min){
min=tempMin;
}
}
dp[start][end]=min;
}
}
System.out.println(dp[0][dataNum-1]);
}
}
}腾讯云开发者
