蓝桥杯算法提高-能量项链-详细分析题解（Java代码）

解题思路:

    其实这道题目相对来说，比较容易。为啥呢？因为，很容易就能分析出它的最优子结构。很容易就能根据最优子结构得到子问题。这里我就来分析一下这个问题的最优子结构吧。

    最优子结构：

        为了方便研究，我把每一个珠子加上编号Ai(0<=i<=N)。珠子是两个两个的释放能量，释放完能量后又合成了一个，可以这样理解。比如：A1=(1,2) A2=(2,3) A3=(3,1)  (A1◎A2)释放之后就 = (1,3)接着与A3结合再释放。它的问题是让我们算出所有珠子最大可以释放多少能量。这个时候我们可以把随便拿一个很小的问题来试试，比如N=1的时候，这个不释放，因为只有一个。N=2的时候，能释放但只有一种组合。

        N = 3的时候，能量链A1 A2 A3，而且是成圆圈的。这个时候，就有三个组合了, (A1◎A2)◎A3 / (A1◎A3)◎A2 / A1◎(A2◎A3)。那我们是怎么分的呢，就是先算两个珠子的，在两个珠子的基础上再加上一个。如果是四个呢，那就算三个珠子，再加上一个珠子就是四个珠子的。这里我们可以描述成分成两份，两份再分...。比如：N=3的时候，分两份是不是只有2个珠子和1一个珠子两种，但是有三种组合。是不是可以从A1 A2 A3中间分，然后只需要找到两份的最优解再相加就得到最后的最优解了。这里就是一个最优子结构了，这里的两份最优解是再同一个位置上的最优解，怎么解释呢....，就是(A1◎A2)◎A3分成了 A1◎A2/A3两份，然后求出左边这份的最优解，右边这份的最优解。合起来就是最优解了。这里看不出来，因为左边是两个珠子，一种组合，右边是一个能量直接=0。

    子问题：

        由最优子结构得到，我们的子问题是份。一开始把珠子分成两份，两份再分，一直分到每一份只有两个或一个珠子的时候就没必要再分了。我们引入一个k，就是代表在哪里分。

        我们再引入一个数组m[i,j]，i代表起点，j代表终点，m[i,j]就是能量和。就比如(A1◎A2)◎A3 可以描述成m[1,3] = m[1,2]+m[3,3] + 新的珠子能量。这里m[1,2]就是A1◎A2释放的能量，m[3,3]就是A3释放的能量(其实=0)，新的珠子能量就是A1◎A2组成的新珠子再和A3释放的能量。这里还要解释一下：为什么A1◎A2可以组成新的珠子...，题目信息,比如 A1=(1,2) A2=(2,3) A3=(3,1) ，A1◎A2之后就得到新的(1,3)了...，然后再和A3结合。

        所有得到那个表达式：m[i,j] = m[i,k] + m[k+1,j] + 新的能量

        但是嘞，注意这里是组成一个圆形：那个A1 A2 A3 中每一个相邻部分都可以组合。A1◎A2 / A2◎A3 / A3◎A1 ，就是这里。

        所以得到新的表达式：m[i,j] = m[i,k%N] + m[(k+1)%N,j] + 新的能量

这个新的能量我直接封装到一个方法里面了，这个就是看规律得到的。

这是最终的：dp[i][j] = Math.max(dp[i][j], dp[i][k%n] + dp[(k+1)%n][j] + p(i,(k+1)%n,(j+1)%n));

public static int p(int i,int k,int j) {   

  return arrays[i]*arrays[k]*arrays[j];
}

说实话，真的不知道怎么解释，我还是举例子吧：A1=(1,2) A2=(2,3) A3=(3,1)这个数据的输入是 N = 3, 1 2 3

(A1◎A2)◎A3  A1◎A2得到新的(1,3)  再和A3(3,1)结合=1*3*1，起点 是A1,分点是A2,终点是A3，i=1,k=2,j=3。哎....点到这里了...

参考代码:

static int arrays[] = null;
public static void main(String[] args) {
  Scanner scanner = new Scanner(System.in);
  int n = scanner.nextInt();
  arrays = new int[n];
  int dp[][] = new int[n][n];
  for (int i = 0; i < arrays.length; i++) {
    arrays[i] = scanner.nextInt();
  }
  //l 是子问题的珠子数
  for (int l = 2;l <= n ; l++) {
      for (int i = 0; i < n; i++) {
       int j = (i+l-1) % n;
       for (int k = i ; k < i + l - 1; k++) {
         dp[i][j] = Math.max(dp[i][j], dp[i][k%n] + dp[(k+1)%n][j] + p(i,(k+1)%n,(j+1)%n));
       }
     }
  }
  int max = 0;
  for (int i = 0; i < n; i++) {
    max = Math.max(dp[i][(i+n-1)%n], max);
  }
  System.out.println(max);
}
//计算组合成新的能量
public static int p(int i,int k,int j) {    
  return arrays[i]*arrays[k]*arrays[j];
}