常用算法思想之动态规划的区间子集思想

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

示例

矩阵线程

给一个矩阵序列 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)的复用，是为了表明结果的可复用性，不需要重复计算

再次回顾上述过程

1. 目标要得到dp(0,3)
2. 需要先计算dp(0,1) dp(1,3) dp(0,2) dp(2,3)
3. 为得到2的结果，需要先获取dp(0,1) dp(1,2) dp(2,3)的结果
4. 为得到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]);
}
}
}
复制代码